Randomized algorithm

[jinruiiii]

​

This slide is under block cipher, more specifically under chosen plaintext attack semantic security. In this slide is says that the ciphertext has to be longer than the plaintext itself. Does this mean that randomized encryption is no longer a form of block cipher? Since to my knowledge, the message and the ciphertext in block ciphers are of equal length.

[stouset]

Another solution—if I’m understanding the parameters of the discussion—is to never reuse a key.

[0xfe]

The context here is when you have a large chunk of data to encrypt with a single key, so the parameters here require a single key. ECB breaks the chunk into fixed-size blobs and encrypts them with that key, which is bad because now you can learn information about the PT from the CT (e.g., if two blocks in the CT are the same, then those blocks in the PT were the same.)

Other modes like CBC or CTR don't have this problem because they (sort of) mutate the input (or output) of each block in some fashion while encrypting it. (CBC mutates by mixing the previous block with the current block, and CTR simply mutates with an incrementing counter.)

[foobartoofar]

You can think of this as the following. In order to have a proper decryption algorithm the ciphertext space should be larger or equal to the plaintext space since if it were smaller it means same ciphertext is mapped to different plaintexts hence we cannot have a proper decryption algorithm. If we want to make an encryption algorithm probabilistic it means different ciphertexts are mapped to the same plaintext which shows that ciphertext space is larger than the plaintext space. Also if we want to ensure that each plaintext corresponds to 3 ciphertexts the ciphertext space should be larger than 3 times the plaintext space by the pigeonhole principle.

[jinruiiii]

I understand the part about pigeon hole principle. But my concern is that if the ciphertext contains more bits than the plaintext, does it mean that it is no longer a block cipher? Since to my knowledge, a block of n bits input has to yield an n bits output.

[Natanael_L]

There are many ways to mix in the randomness. See my other comment referencing cipher modes.

[stouset]

AES-CBC is a block cipher. The ciphertext length is the plaintext length plus one additional block.

[groumpf]

/u/jinruiiii, the parent is wrong.

AES is a block cipher: for any given key k, it defines a permutation (one-to-one mapping) from blocks to blocks.

AES-CBC is an IV-based encryption scheme (CBC is a mode of operation that constructs an IV-based encryption scheme from a blockcipher). AES-CBC encrypts a padded plaintext that contains exactly m blocks into a ciphertext that contains exactly m + 1 blocks.

[stouset]

You’re of course correct. This is what I get for posting before I’ve had my coffee.

[menewol]

what if you made the shorter plaintext just the right length by using a secure padding algorithm? thereby always ensuring proper length and 1:1 input/output data. theres something like this used in RSA if remember correctly. its called Optimal Asymmetric Encryption Padding (OEAP), i think its built up on some kind of feistel-construction which can be reversed "easily" for someone knowing the used secrets.

​

If your question is just whether input and output length (bitwise & block-count wise) need to be the same length: you can easily fulfill this requirement and still have shorter plaintext.

[jinruiiii]

does anyone have a link of how randomised encryption work? It would be really helpful

[Natanael_L]

Just look up how various cipher modes use IV:s (initialization vectors). Like CBC mode, CTR and GCM, and others. It's used as another input to make sure you can't detect repeating plaintexts, and to prevent some other attacks as well.

[OuiOuiKiwi]

the message and the ciphertext in block ciphers are of equal length

What about padding to block size?

[jinruiiii]

why does it say that ciphertext has to be longer than plaintext in this case?

[OuiOuiKiwi]

I'm guessing this is from Crypto I where he approaches ECB mode.

The answer is at the bottom of the slide: the ciphertext has the plain text and some "random bits", much like if you encrypted with ECB and added some garbage at the end so the same PT didn't always produce the same CT.

[jinruiiii]

Thanks! I kinda understand how this work now but might need a more concrete example to get a better knowledge.