[97228] in cryptography@c2.net mail archive
magnifying unpredictability and common subexpressions
daemon@ATHENA.MIT.EDU (travis+ml-cryptography@subspacefie)
Wed Aug 8 11:28:58 2007
Date: Tue, 7 Aug 2007 07:58:39 -0500
From: travis+ml-cryptography@subspacefield.org
To: cryptography@metzdowd.com
Mail-Followup-To: cryptography@metzdowd.com
--MGYHOYXEY6WxJCY8
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
So I'm looking for a minimum cost transformation with _only_ the
following characteristic:
Given a set of m input bits X, produce a set of n output bits Y such
that knowledge of some subset of X and Y gives a minimum knowledge of
the remainder (of Y if that makes it simple, but of X would be nice).
This is not unlike the "all-or-nothing" package transform proposed
by Rivest; the basic idea is that you have to know all of X in order
to know anything about Y - sort of.
My first iteration is as follows:
Let ^ represent xor.
Let p be the exclusive or of all bits of x (i.e. the parity).
Let Y =3D f(X), where f(x) =3D p ^ x
Basically, each bit of Y is the xor of every _other_ bit of x
(x was actually xored into p, so by xoring again, it cancels out)
However, my problem is that no matter how few bits of X you know, you
only have to guess one bit, p, in order to know the bits of Y that
correspond to the bits you know of X.
Let me be concrete; suppose that I know only bits 0 of X and bit
0 of Y. I can then compute p, and from that I can use any further
knowledge of bits of X to compute corresponding bits of Y.
Note that p =3D x[0] ^ y[0].
Then if I know x[1], I can reveal y[1] =3D p ^ x[1].
And so forth.
Obviously I need something more complex. The problem seems to be that
the equations for every bit y depend only on x and p; that is, if we
know x, we only have to guess p once for the whole array.
In a way, this reminds me of an idea I had earlier, whereby this
variable p is what I call a common subexpression, a key which unlocks
the equation, a sort of trapdoor.
Suppose I had written Y =3D f(X) as follows:
y[0] =3D x[1] ^ x[2] ^ x[3] ^ x[4]
y[1] =3D x[0] ^ x[2] ^ x[3] ^ x[4]
y[2] =3D x[0] ^ x[1] ^ x[3] ^ x[4]
=2E..
A novice may have not have realized that each bit of y depends _only_
on x ^ p, and that knowing or guessing p would reveal every bit of Y
for each known bit of X, without having to know any other bit of X.
Now, what I sometimes wonder is whether the equations and tables in
things like DES or SHA-1 are not similar... a table allows for several
boolean logic representations, and depending on which you pick for
each output bit, it may be possible that a common subexpression like p
falls out of the equations, minimizing the amount of unknowns, or
the amount of compute power necessary to brute-force it.
For a Feistel cipher like DES, one might pick different boolean logic
representations in different rounds, to minimize the complexity of
the equations you get at the end.
This is why I don't try to design ciphers. I could possibly come up
with some complicated-looking tables and equations, but I'd have no
assurance that a simple common subexpression did not exist.
Do I need to resort to a conventional hash like SHA-1? I am not
convinced that it is necessary, or that I'd have any more assurance
=66rom SHA-1 than I'd have with a randomly-generated set of equations.
Does it have to be random? Isn't there a regular structure I could
exploit here? It seems like there should be!
Randomly-generated equations remind me a bit of the following AI Koan:
In the days when Sussman was a novice, Minsky once came to him as he
sat hacking at the PDP-6.
"What are you doing?", asked Minsky.
"I am training a randomly wired neural net to play Tic-Tac-Toe",
Sussman replied.
"Why is the net wired randomly?", asked Minsky.
"I do not want it to have any preconceptions of how to play", Sussman
said.
Minsky then shut his eyes.
"Why do you close your eyes?", Sussman asked his teacher.
"So that the room will be empty."
At that moment, Sussman was enlightened.
--=20
<URL:http://www.subspacefield.org/~travis/> -><- dharma <>< advaita
For a good time on my UBE blacklist, email john@subspacefield.org.
--MGYHOYXEY6WxJCY8
Content-Type: application/pgp-signature
Content-Disposition: inline
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (OpenBSD)
iQIVAwUBRrhsf2QVZZEDJt9HAQKW2w//QMa9JyxZhKjS/oUfCy8nXD2qw5vR2W2I
zI0uxGPWPwfeHn6ZLIzVdWjqKZvVlzLPn6JZvAK1XzJXU8sSMyDLMa2EVO/T6vH+
jAD7XTy4bR03CL/6gthoZcVO42MiRnBLakjlVTebO2nfbdElPv4PUIzxILcYZGRA
6eGbcT3iHSNvRKTWenIlbrVXqKvUmT4wKAwON5kAX3+t05gbL5AIAXU05cy9cMMy
krN65r+pgwwdI3MBguH4+C64vlRrtflb68NaQzsQiwDBLhmuC4SQz9Xlx9rinwaQ
nQEhoFYQ1ecbsfsDFgTk5f+egCpWw8CYjwWq671X4RNXMM4zga5uC/KcMwt5PA/b
nFxeGFiATfQ+FLOKKP0LqEEwc0Y/fwGcqsKRN4SnX8uHeWJnZG4aq0fMOhYleeEi
FFzUU5kAfzK4Iw2Nby5Cmmr8GY5ydFm7SuIHYZkV4pDu/YU54zyldCEXRAKdeOKd
Bz80o6MKkDmry/2MWEH1VjmSZ+u+NHXKabtcEA2abgwODBNVXR2R84a9695EAOEG
fzZPjVO2nBtJ8GbfFcqr8R/2QCPKg3Ha7iywQHLJTvdvjYQyIITgq2+wVTJnZDOS
v/nkt5rLwBabkgTOqCT5eARLWKnByfYnUtnftBGv8AmISnWtAncb/ZQQ2WXE0LjB
tItLLc9u40o=
=sD0h
-----END PGP SIGNATURE-----
--MGYHOYXEY6WxJCY8--
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
