[20376] in cryptography@c2.net mail archive
Re: bounded storage model - why is R organized as 2-d array?
daemon@ATHENA.MIT.EDU (alex@alten.org)
Thu Mar 9 09:42:11 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: alex@alten.org
To: "Travis H." <solinym@gmail.com>, cryptography@metzdowd.com
Date: Thu, 09 Mar 2006 02:10:58 -0500
> ----- Original Message -----
> From: "Travis H." <solinym@gmail.com>
> To: cryptography@metzdowd.com
> Subject: bounded storage model - why is R organized as 2-d array?
> Date: Thu, 2 Mar 2006 23:06:41 -0600
>=20
>=20
> Hey,
>=20
> In Maurer's paper, which is the last link here on the following page,
> he proposes to use a public random "pad" to encrypt the plaintext
> based on bits selected by a key. What I'm wondering is why he chose
> the strange construction for encryption; namely, that he uses an
> additive (mod 2) cipher where each plaintext bit is (apparently) XORed
> against K bits from the random pad. He also uses a 2-d array
> structure, both of which appear kind of arbitrary to me.
>=20
> http://www.crypto.ethz.ch/research/itc/samba/
>=20
This is a subject that I'm painfully familiar with. Dr. Maurer has=20
slowly but surely over the last decade or so been putting together
a solid proof of a cipher very similar in construction to Dr. Atalla's=20
proprietary Tristrata cipher (US patent #6088449). The basic idea=20
is that you do something like random1 XOR random2 =3D pad, then pad XOR
plaintext =3D ciphertext. If random1 and random2 are arrays of bits=20
(n-bit random numbers) from a much larger amount of random material,=20
then one can tune the probability of the pad repeating to be almost
zero. Essentially you get an equation with 2 unknowns (pad and=20
plaintext), which is pretty hard to solve if the pad is hard to=20
determine. The 2-D array simplifies getting the randomX's.=20=20
Basically you treat the initial random material as a big array of N=20
random bit strings. Each randomX value is a random strip inside=20
each bit string. Each strip is the same size (at TriStrata we=20
typically used four 64-Kbyte strips, each from a 250 Kbyte bit=20
string). You XOR them together and get a "random" pad (ours was 64=20
Kbytes long). We were able to XOR about 32 Kbytes of plaintext into
ciphertext, before an inverse matrix attack became feasible. Then=20
a new pad had to be generated for the next 32 Kbytes.
The reason people like Dr. A or Dr. M are interested in doing this
is because you can get super-fast ciphers or get some sort of=20
fundamental proof about its strength that is applicable to all types
of ciphers. The speed, from a software engineering perspective,=20
results from the classic tradeoff between memory lookup and execution=20
loop complexity. If one can get down to a couple of XORs and memory
copies (per 32 or 64 bit data)using ordinary microprocessor=20
instructions then it will outperform AES by around a couple of orders
of magnitude. This is very useful for encrypting things like video=20
streams without an expensive hardware cryptographic accelerator card.
Dr. M showed in an earlier paper that if one uses enough randomX=20
values that you can get arbitarily close to generating a truly random
pad each time you need it to encrypt some ciphertext (but with N XORs!).
Anyway, the big negatives are that with this type of Vernam cipher
the entropy decays really fast, especially if the initial big source
of random bits is publicly known, the pad management is really hairy,=20
and generating lots of random bits of the initial material is very=20
slow. Huge numbers of pads have to be generated and distributed all=20
the time, and a great deal of care has to be taken to mitigate the=20
cipher's decaying strength and to avoid several types of attacks on=20
the pad generation.
It is of great personal interest to me to watch Dr. M slowly prove=20
that the underlying mathematics of Dr. A's Tristrata cipher may not=20
have been snake oil after all.
- Alex
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
