Re: Encryption key longer than text to encrypt




Unruh wrote:
"=?iso-8859-1?q?Jean-Fran=E7ois_Michaud?=" <cometaj@xxxxxxxxxxx> writes:


rossum wrote:
On 5 Jan 2007 13:31:41 -0800, "Jean-Fran=E7ois Michaud"
<cometaj@xxxxxxxxxxx> wrote:

Hmmm, I can't help but notice the similarity between a synchronous
stream cipher where the keystream generation is independant from the
acutal XORing process.

In such a context, the OTP key and the keystream share the same idea,
notably that a large key/keystream will be XORed against plaintext.
This is why I'm coming back to OTP, because, the OTP being a perfect
case and being contextually clear and well understood, I feel it makes
thinking easier than to lay down the context of a synchronous stream
cipher in which the keystream generation is independant from the XORing
process.
There is a fundamental difference between an OTP and a keystream
generated from a key. Say you have a 128 bit key, then there are
2**128 possible keys, each of which generates a different keystream.
Hence there are 2**128 different keystreams possible in this cypher.
Say we have a 2KB message to encrypt. We use the first 2KB of one of
our 2**128 keystreams.

Now think about an OTP encrypting a 2KB message. There is no
generated keystream, just a random key as long as the message (or
message + padding). That means that in the OTP there are 2**2048
possible different 'keys', which equates to 2**2048 possible different
keystreams. As soon as you move from an OTP to a generated keystream
you have a drop in the possible number of different keys allowed. In
the OPT case the attacker has 2**2048 different keystreams to try,
with a keyed cypher she only has 2**128 different keystreams to try.

With the keyed cypher, all the entropy is in the key - once you know
(or guess) the key, there is no additional entropy in the generated
keystream. Working out the keystream from the key is a matter of pure
computatation, as it has to be if decryption is to work correctly.
With the OTP the key is identical to the keystream so all of the
keystream is entropy. That is why for an OTP you need to send the
keystream in its entirety as it cannot be generated by any algorithm.

A stream cypher is certainly more practical than an OTP, but it is not
merely a version of an OTP - it is an entirely different animal.

Right, I clearly understand the difference between both, and I also
clearly understand that the bottleneck for a stream cipher is the key
and not the generated keystream and that the strenght of the key varies
with the lenght of the message for the OTP (so does the strenght of the
key in this case); those differences set asside, the OTP key and the
keystream are used for the same purpose (being XORed against
plaintext). So, an otherwise interresting idea for OTP, could also most
probably be directly applied to stream ciphers, hence the idea of
concealing the lenght of the message by having a message that is
smaller than the OTP key or stream cipher keystream.

It's nice to see that you're not so enclined to trying to tear me
appart anymore. We might be able to actually have a dialog :-/.

Certainly padding the message is a good ( and old) idea for any stream cypher, whether
OTP or not. However there is no advantage to padding with a random stream
or all zeros for an OTP. It makes no difference whatsoever to the strength
of the OTP.

I would have a tendency to disagree (of course padding with zeros would
be useless, and even harmful because it could give a clue to an
potential attacker, but I had something else in mind, it seems to me
that it would amount to something.

Take the following example:

Imagine an OTP. Lets say 2KB of perfectly random data (key) and another
(2KB - 24 bits) of perfectly random data (used for padding). 3
character from the plaintext message are inserted where the missing 24
bits would be (assuming 8 bit characters. The missing 24 bits could be
dispersed around as randomly as the random padding data to avoid
sequential plaintext data). Now imagine that through some miracle the
attacker is able to brute force through all the keys and has all the
possible decryption at his disposal for every encrypted message
(imagine a message 15 characters long for example, this would yield 5
encrypted messages, sent across). What is the initial assumption? Full
message length, he gets nowhere.

Now imagine we give the attacker invaluable information. The
information that only 3 characters of plaintext are encrypted but he
doesn't know where. What can he do? He has to figure out what those
characters are through as many unencrypted messages as the keyspace is
large and he has to try out every combination of blocks of 3 characters
per keyspace across each keyspace per intercepted messages ranging over
a whole slew of messages (5 in our example). We have a combinatorial
explosion that is many orders of magnitudes greater than what standard,
straight up, OTP itself allows as far as protection goes. We are
magnitudes beyond being "unbreakable".

Am I missing anything?

I'm simply thinking that a similar scheme would be extremely useful in
compensating to the looser encryption strenght of stream ciphers. And
If the idea is sound, I would even go as far as saying that key
information exchange could be performed very safely through such a
channel.

[SNIP]

Regards
Jean-Francois Michaud

.



Relevant Pages

  • Re: Encryption key longer than text to encrypt
    ... stream cipher where the keystream generation is independant from the ... In such a context, the OTP key and the keystream share the same idea, ... Hence there are 2**128 different keystreams possible in this cypher. ...
    (sci.crypt)
  • Re: Encryption key longer than text to encrypt
    ... In such a context, the OTP key and the keystream share the same idea, ... clearly understand that the bottleneck for a stream cipher is the key ...
    (sci.crypt)
  • Re: Chosen plaintext attacks
    ... Similarly an PRP cipher relies on the fact that the internal keystream ... If the PRNG is leaking information about its internal state then it ... That depends on there being no other weaknesses in the PRNG. ... Well that would work for an OTP also you will have the OTP key, ...
    (sci.crypt)
  • Re: Encryption key longer than text to encrypt
    ... the generated keystream is completely ... keys that exceed plaintext in a context where plaintext is intermixed ... an OTP does not use a generated keystream but uses a very ... glow of the security of the OTP onto the dross of their bad stream cypher. ...
    (sci.crypt)
  • Re: Encryption key longer than text to encrypt
    ... the generated keystream is completely ... the context I'm interrested in is not this one. ... an OTP does not use a generated keystream but uses a very ... Padding, gottcha;-). ...
    (sci.crypt)