What does the Comma Notation in the textbook “Serious Cryptography” describing DRBGs mean

cryptographynotation

I'm going through Serious Cryptography: A Practical Introduction to Modern Encryption by Jean-Philippe Aumasson. In the first chapter we have this:

One of the simplest constructions of a semantically secure cipher uses a deterministic random bit generator ($DRBG$), an algorithm that returns random-looking bits given some secret value:

$E(K, R, P) = (DRBG(KR) ⊕P, R)$

Here, $R$ is a string randomly chosen for each new encryption and givento a DRBG along with the key ($K || R$ denotes the string consisting of $K$ followed by $R$)

Can anyone explain to me what the $(DRBG(KR) ⊕P, R)$ part means? (K = Key, R = random bits, P = Plaintext)?

In particular what is confusing me is the following:

  • Is the second paragraph trying to say that DRBG(KR) is actually DRBG(K || R)? (in which case I assume '||' means concatenate, not 'OR')
  • What does the '$, R$' mean in the left hand side of the formula? There's no function prefix at the start of it so I'm not sure what the R is being used for, is it trying to say that $E(K, R, P) = E(DRBG(KR) ⊕P, R)$? If that's the case then it doesn't match the arguments anymore for E

Best Answer

A Deterministic Random Bit Generator (DRBG) is a random bit generator such that when the same seed is given the output will be always the same.

Can anyone explain to me what the $E(K, R, P) = (\operatorname{DRBG}(K||R) \oplus P, R)$ part means?

It means

  • seed the $\operatorname{DRBG}$ with concatenating the key $K$ and random $R$
  • output $len(P)$ amount of random bits ( call it as Key Stream (KS))
  • $\oplus$ the key stream with the plaintext $C = P \oplus KS$
  • return $C$ and $R$.
  • send or store $(C,R)$.

Is the second paragraph trying to say that DRBG(KR) is actually DRBG(K || R)? (in which case I assume '||' means concatenate, not 'OR')

Yes, there is a typo there since $DRBG(K \oplus R)$ is distinguishable by $DRBG(K \oplus R)$ and $DRBG(R \oplus K)$ but $||$ is not with a fixed key.

  • What does the '$, R$' mean in the left hand side of the formula? There's no function prefix at the start of it so I'm not sure what the R is being used for, is it trying to say that $E(K, R, P) = E(DRBG(KR) ⊕P, R)$? If that's the case then it doesn't match the arguments anymore for E

The $R$ is similar to nonce/IV of the block/stream ciphers so that one can use the same key $K$ more than once. As in the nonce/IV case you need to send it so that the receiver will use it during the decryption where here as in OTP, it is the same process.

The crucial part is the $K||R_i$ and $K||R_j$ must not overlap for $i \neq j$. If overlapping occurs (two-time pad), the crib-dragging technique can be used to reveal the plaintexts and it can be automated;

Related Question