[Cryptography] Guaranteeing that no distinct keys produce indistinguishable results

Ray Dillinger bear at sonic.net
Wed May 27 20:38:45 EDT 2015

There's a tiny problem with a fair number of ciphers and
deterministic pseudorandom bit generators, which is that
two different keys or different sequences of entropy input,
can posssibly result in the same encryption or the same
sequence of pseudo-entropy output.  In fact there's a
related issue with DES, where the effect of composing
any two encryptions with different keys is the same as
a single encryption with a third key (hence 3DES with
a DEcryption in the middle rather than another ENcryption
that wouldn't actually add anything to security).

In fact this is the norm for pseudorandom bit generators,
because the design space favors a fixed-size buffer of
state and mechanisms to permit any amount of input to be
fed into it.  It is astronomically unlikely in PRNGs with
large state, but you can't actually prove that two different
sequences of input won't result in the same state.

I was thinking about this the other day and implemented a
cryptographic peculiarity; a deterministic PRNG (usable for
stream ciphers) that guarantees a different state (and
therefore output sequence) for every possible different key.

Its design is very simple:  It's the "Spritz" generator by
Rivest and Schuldt, with a state size depending on the size
of the key input and a key schedule which guarantees that no
distinct keys of the same length result in identical initial
states.  It is also impossible for any key to create a
state that "leads" or "trails" the state that a different
given key results in and produce the same sequence of
outputs shifted a finite number of outputs earlier or later.

Does anyone have a use for this cryptographic peculiarity?


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150527/97585637/attachment.sig>

More information about the cryptography mailing list