[cryptography] The Unbreakable Cipher

Eugen Leitl eugen at leitl.org
Wed Sep 25 10:49:40 EDT 2013


On Wed, Sep 25, 2013 at 10:11:33AM -0400, John Young wrote:

> Is this conclusion still valid? If so, what could be done to restrict traffic
> volume to assure unbreakablility? And how to sufficiently test that.

You need to be able to estimate the rate of information leakage.
This seems to be related to measuring RNG entropy, and is considered 
a hard (perhaps hopeless?) problem. 

> Presuming that NSA and cohorts have investigated this effect.

It seems to be possible to construct a family of cyphers based
on PRNGs with Very Large Internal State (the shared key is the 
state) that asymptotically approach (in a special/edge case are
exactly equivalent to) one-time pads. You'd tap them for XOR
with cleartext through a relatively small (=plenty of hidden
state) window (not necessarily contiguous) and use enough 
iteration rounds to make sure the information
has has a chance to propagate through the computational 
volume. Edge cases are low-dimensional CAs with a suitable
rule, which should be easiest to attack. Higher-dimensional
CA analoga have a lot of neighborhood cells, and their map to
address space looks like a small world network, so state
mixes quite rapidly, requiring fewer rounds. Whether making 
neighborhood itself random versus orthogonal is helping or 
hindering things is not obvious. Whether to make the neighborhood 
itself subject to change at each or N rounds is helping or 
hindering things is not obvious.

The actual problem is to build them provably hard to reverse,
and rekey (though a secure channel, natch) before they leak
enough information about their inner state to be attackable.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: Digital signature
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20130925/0c33f477/attachment-0001.asc>


More information about the cryptography mailing list