4
$\begingroup$

If I let the authentification tag aside (which is important), encrypting with AES-GCM and a fixed key and nonce:

import Crypto.Random, Crypto.Cipher.AES, numpy as np
key = bytes.fromhex('7d29ccf69c671775e17d4b9dd6485fd8')
nonce = bytes.fromhex('04972c7927042af0ee10c7e6ac56ddd3')
cipher = Crypto.Cipher.AES.new(key, Crypto.Cipher.AES.MODE_GCM, nonce=nonce)
print(cipher.encrypt(b'goodgoodcrypto').hex())     # e7e4d3b74617d78022376651ba3a

can be obtained with the same result by obtaining a cipherstream (encryption of a stream of \x00\x00... null bytes) to XOR with the plaintext

xor = lambda x, y: (np.frombuffer(x, dtype='uint8') ^ np.frombuffer(y, dtype='uint8')).tobytes()
cipher = Crypto.Cipher.AES.new(key, Crypto.Cipher.AES.MODE_GCM, nonce=nonce)
cipherstream = cipher.encrypt(b'\x00' * 14)     # 808bbcd32178b8e441451f21ce55
print(cipherstream.hex())
print(xor(cipherstream, b'goodgoodcrypto').hex())   # e7e4d3b74617d78022376651ba3a !! same ciphertext!

Here I only took 14 bytes of cipherstream because I only needed 14 bytes to encode plaintext.

Thus, it looks like in this context of AES-GCM that:

  • encryption here is equivalent to just having a long-enough stream of random-looking bytes (cipherstream above),
  • deterministically initialized with key and nonce (similar to the seed in PRNG terminology)
  • encryption is just this cipherstream XORed with plaintext

Question: can we turn a (cryptographically secure) PRNG into a stream cipher? (the PRNG's seed is the key / nonce)

The reciprocal seems also true: AES-GCM encrypting a flow of null bytes b"\x00\x00\x00\x00..." seems to give a cryptographically secure PRNG. The seed is the key+nonce pair.

$\endgroup$
2
  • $\begingroup$ I see you set up a bounty looking for something canonical. Is there anything missing in my answer? $\endgroup$
    – DannyNiu
    Apr 26, 2022 at 5:47
  • $\begingroup$ @DannyNiu Your answer is very good (BTW I should have chosen "Add details" instead of "Canonical" for the bounty). 1) It would be great to have more details or examples or links about the terms ("post-compromise reseeding", "back-tracing resistance" etc.) to help the understanding. 2) In the specific example of AES-GCM, is it true that encrypting a flow of null bytes \x00\x00... gives a CSPRNG, for which the seed is the AES key+nonce pair? $\endgroup$
    – Basj
    Apr 26, 2022 at 7:22

1 Answer 1

8
+100
$\begingroup$

Stream cipher and CSPRNG aren't the same thing. CSPRNGs must handle initial seeding, post-compromise reseeding, back-tracing resistance among other things; stream ciphers only need to be able to output something indistinguishable from random.

For example, the reseeding process should fulfill 2 requirements: if the original seed is compromised, adding new entropy restores the security of the CSPRNG; if the new seed is weak or compromised, the existing seed must continue to provide security.

For back-tracing resistance, one does not want compromise of the current state of the CSPRNG to allow adversary to obtain randomness generated in the past.

These requirements are discussed extensively in section 8 of NIST-SP-800-90Ar1

In the specific example of AES-GCM, encryptin a flow of nul bytes indeed give an initial segment of a CSPRNG (because there's no re-keying to protect it from back-tracing resistance). The seed material is the key+nonce pair - emphasize on the "material" part of the seed because the NIST SP describe it (the combination of entropy input, personalization strings, nonces, etc.) as "seed material".

So can we turn a CSPRNG into a stream cipher? Possibly, if we make every generate requests to the CSPRNG idempotent, and drop reseeding. But that wouldn't be as efficient as just using the stream cipher directly - not only does CSPRNGs has extra code paths to execute, its internal state is often larger than that of stream ciphers.

$\endgroup$
1
  • 1
    $\begingroup$ To note that I'm talking about what NIST considers as a PRNG - NIST-SP-800-90 deterministic random bits generator. $\endgroup$
    – DannyNiu
    Dec 1, 2020 at 6:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.