0
$\begingroup$

I am currently taking Dan Boneh's Cryptography I course online. I have just finished the segment discussing the Cipher Block Chaining and Counter-Mode. I am having difficulty understanding why Ctr-Mode works as an encryption algorithm as PRFs are fundamentally non invertible, as per my understanding. Any clarification on this would be highly appreciated!

$\endgroup$
  • $\begingroup$ For any length, $\: \langle$ binary_strings_of_that_length , xor $\rangle \:$ is an abelian group. $\hspace{1.92 in}$ For any length, each element of that group is its own inverse. $\;\;\;$ $\endgroup$ – user991 Nov 12 '15 at 23:51
  • 1
    $\begingroup$ @RickyDemer I've generated an answer without (too much) math in it, but I would happily vote up an answer that explains the mathematics behind it. $\endgroup$ – Maarten Bodewes Nov 13 '15 at 0:55
2
$\begingroup$

CTR consists of two parts: construction the key stream using a counter, and XOR-ing the output of the key stream with the plaintext/ciphertext. The key stream can be generated using a PRF, in which case it is of course not invertible. The key stream can also be created using a PRP (e.g. a block cipher like AES) in which case it is invertible.

As indicated, CTR mode encryption requires the XOR-ing of the plaintext / ciphertext as well. A PRF is a pseudo random function, so given the same input it will generate the same key stream. The XOR-ing of the key stream is perfectly reversible; you just have to perform the XOR with the key stream again. So CTR mode encryption is always reversible, even when it relies on a PRF to generate the key stream.

Because of this, CTR-mode is indeed not a PRF.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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