# If PRF is non invertible, why does Ctr-mode work?

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!

• 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. $\;\;\;$
– user991
Commented Nov 12, 2015 at 23:51
• @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. Commented Nov 13, 2015 at 0:55

## 1 Answer

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.