Cryptography-Digest Digest #825, Volume #13 Wed, 7 Mar 01 03:13:01 EST
Contents:
Re: Sad news, Dr. Claude Shannon died over the weekend. (John M. Gamble)
Re: Super strong crypto (David Wagner)
Re: super strong crypto, phase 3 (David Wagner)
Re: beyond "group signatures": how to prove sibling relationships? (Benjamin
Goldberg)
Re: super strong crypto, phase 3 (John Savard)
Re: Super strong crypto ("Douglas A. Gwyn")
Re: super strong crypto, phase 3 ("Douglas A. Gwyn")
Re: Sad news, Dr. Claude Shannon died over the weekend. (Dennis Ritchie)
Re: How good is the KeeLoq algorithm? (Paul Crowley)
Re: Any news on the KFB mode? (Paul Crowley)
Re: Monty Hall problem (was Re: philosophical question?) (Dave Moore
[EMAIL PROTECTED]>)
Re: sci.crypt? ("Greg Ofiesh")
Re: sci.crypt? (David A Molnar)
Re: PKI and Non-repudiation practicalities ("Lyalc")
Cipher idea (Benjamin Goldberg)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John M. Gamble)
Subject: Re: Sad news, Dr. Claude Shannon died over the weekend.
Date: 7 Mar 2001 04:55:12 GMT
In article <9801h1$2kg2$[EMAIL PROTECTED]>,
Derek Bell <[EMAIL PROTECTED]> wrote:
>Volker Hetzer <[EMAIL PROTECTED]> wrote:
>: "John A. Malley" wrote:
>:>
>:> I heard on NPR today that Claude Shannon died this past weekend at the
>:> age of 84.
>: Wow, I didn't know that he was still around. Most other people
>: that founded a whole new science died centuries or even millenia ago.
>: I think I'll have a quiet beer on him this evening.
>
> I didn't know he was still alive either - pity he's died!
>
> Derek
According to the NYT obit, he suffered from Alzheimer's. So he wasn't
much in the public eye for the last years of his life.
It's a shame. From the description in the obit, he was a lively fellow.
One wonders if anyone else ever pogo-sticked down the Bell Labs hallways?
-john
February 28 1997: Last day libraries could order catalogue cards
from the Library of Congress.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Super strong crypto
Date: 7 Mar 2001 05:04:41 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Douglas A. Gwyn wrote:
>David Wagner wrote:
>> Could you define "reasonable mixing properties", please?
>
>Essentially as indicated by the name -- each bit of the output
>is a function of *every* input (PT and key) and vice-versa for
>the (generalized) inverse, such that there are 2^sizeof(k)
>solutions distributed fairly evenly among all the input bits,
>for on the order of (2^sizeof(k))/sizeof(x) possibilities for
>*any* given PT bit.
I must admit I don't quite understand what the latter part of
your condition is driving at (it speaks of solutions, but solutions
to what equation?). Still, maybe we should just try an example.
Does the following cipher satisfy your conditions? Consider:
E_k(x) = AES_0(F_k(x)),
where F_k(x|y) = (DES_0(x) xor k) | (DES_0(y) xor k),
where DES_K(P) denotes the DES-encryption of plaintext P under key K,
and similarly for AES_K(P),
and where x|y denotes the concatenation of x and y.
Observe that every bit of E_k(x) depends (in a complex way) on
every bit of k and x, and similarly for decryption. Nonetheless,
your mode is insecure when used with this E().
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: super strong crypto, phase 3
Date: 7 Mar 2001 05:15:10 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
By the way, maybe I can ask one more question.
Q: Are you assuming that your block cipher can resist
all known-plaintext attacks, when the adversary is
given only a single block of text?
When you speak of using a block cipher with a 256-bit block
and a 128-bit key (for instance), it seems that you may be
making this "one-block" assumption.
But if you are, let me mention the following subtlety.
If there exists a block cipher E_k(x) with 2n-bit block and
n-bit key that satisfies the above assumption, then there
is no need for a new construction to build super-strong crypto.
Indeed, under such an assumption, there already exist well-known
constructions for building modes of encryption that are _provably_
secure (in a way that can be made precise and rigorous).
One example of such a provably secure mode proceeds as follows.
Define G(k) = E_k(0). Note that G : {0,1}^n -> {0,1}^2n is a
secure pseudorandom generator, i.e., a secure way of stretching
a n-bit secret key to a 2n-bit output; if E_k(x) satisfies the
"one-block" assumption, it is impossible to efficiently distinguish
the output of G() from a uniformly random 2n-bit stream.
Now we can build PRGs that expand their seed by any desired factor.
For example: we let k1|k2 = G(k) and define G'(k) = G(k1)|G(k2),
where x|y denotes the concatenation of x and y. Then
G' : {0,1}^n -> {0,1}^4n is a secure PRG. This idea may be repeated
as far as desired. Then we may use this as a keystream generator
and xor its output against the plaintext (i.e., as a "stream cipher",
in the academic usage).
If you don't like keystream generator modes, you can build a
pseudorandom function from G using a standard construction, covered
in any course on provable security, and from this you can construct
a block cipher E'() that is provably secure against all efficient
chosen-text attacks if E() was secure against all single-block
known-text attacks.
All of the above statements may be proven. See a good course on
provable security (e.g., Bellare and Goldwasser's course notes).
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: beyond "group signatures": how to prove sibling relationships?
Date: Wed, 07 Mar 2001 05:18:20 GMT
David Wagner wrote:
>
> Fen Labalme wrote:
> >the players (sorry if the notation is non-standard):
> >
> >T a "parent" public key pair
> >
> >use of T's secret key may be involved in the generation of its "child" nyms:
> >
> >Ci a "child" of T (public key pair) named "i"
> >Cj a "child" of T (public key pair) named "j"
> >Ck a "child" of T (public key pair) named "k"
> >
> >desired properties:
> >
> >1) Ci, Cj, Ck cannot prove who its parent (T) is
> >
> >2) Ci, Cj, Ck cannot prove they are siblings
> >
> >3) T can prove parenthood of children (e.g. Ci, Cj, and/or Ck)
> >
> >4) T is able to prove Ci and Cj are siblings
>
> I don't understand; is there something more?
> Maybe you mean that Ci,Cj,Ck are supposed to be able to sign
> statements so that the signature can be verified using T's public
> key, and so that the signature do not reveal which child signed
> the message? Did you mean to require something like that?
I don't think so. I think that T, C[i,j,k] are supposed to be keypairs,
and all are capable of signing/verifying/encrypting/decrypting messages,
just as if they were normal PKE keys.
Parenthood and sibling hood might be useful for something like:
You've got a secret society, with a grassroots / secret cell
organization. None of the members (C[i,j,k]) can identify their cell
leader (T), or each other (1 and 2), but the cell leader can prove that
he is their leader (3). Also, he can prove to two members (who
previously did not know that the other was a member) that other is a
member (4). Also, the cell leader's introduction of two members to each
other can be done without identifying himself (4a) or identifying any
other members (4b).
(1) Could be elaborated as meaning that, even with full collaboration,
(knowing all of C[i,j,k]'s public and private keys), the children cannot
identify T's public key (identify == prove that a given public key is
their parent's public key).
(2) Mean that even with knowing all of C[i,j,k]'s public and private
keys, it is impossible to prove that any of them are siblings.
(3) Means that someone with T's keypair can prove (either to just one of
T's children, or to the world in general) that a particular keypair (one
of C[i,j,k]) was derived from T.
(4) Someone with T's keypair can prove to Ci that Cj is his sibling,
*even without trusting T*. In the secret cell scenario (say that three
times fast!) this means that if the cell leader becomes compromised
(forced to write messages, or perhaps his key is stolen and someone is
trying to spoof him), the damage is limited. Only if Ci and Cj truly
are T's children should T be able to prove to them that they are
siblings.
With a simple, trust-requiring system, one might try to accomplish (4)
by having T prove his identity to Ci, claim to Ci that Cj is a member,
and say to Ci, "trust me." This is weak, but if you do trust T, it
works. In a good system, if Ci and Cj get T's key, they can prove to
themselves they are siblings, without giving away their private key info
to each other, without needing any third party, and without needing to
trust anyone.
(4a) T should be able to create some kind of certificate, readable only
by Ci which proves Cj is his sibling, without giving away any
information about himself, not even what his public key is, and still
not requiring that Ci trust T. I think this is a slightly stronger
requirement than what was originally stated for (4a), but it is quite
close to what is meant... just send a message to both Ci and Cj telling
each other that they are siblings.
And what (4b) means should be fairly obvious.
--
The difference between theory and practice is that in theory, theory and
practice are identical, but in practice, they are not.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: super strong crypto, phase 3
Date: Wed, 07 Mar 2001 04:59:50 GMT
On Wed, 07 Mar 2001 04:08:21 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote, in part:
>Starting with an unrecoverable situation due to insufficient
>information, the above implies that the situation remains
>unrecoverable (always insufficient information). True, it's
>hand-waving, but plausible hand-waving.
If you have
E(P1,K1)
E(K2,K1)
E(P2,K2)
E(K3,K2)
E(P3,K3)
E(K4,K3)
E(P4,K4)
...
and the size of each of the Ps is short enough that there isn't enough
information to find one of the Ks from that one P,
since K2, K3, K4, K5, ... are all strictly determined by K1 if you
have the ciphertext,
you don't have always insufficient information; instead of just P1,
you also have P2, P3, P4, ...
brute-force search is possible = enough information exists for
cryptanalysis.
How, though, would one exploit the connection between keys using an
analytic approach instead of brute-force search? Each plaintext chunk
is encrypted through a key that is in itself unrelated; the connection
is simply that the ciphertext includes a copy of that key enciphered
in the previous key.
That's the question: can it be shown that this type of connection is
harder to attack than the one created by something like simple double
encryption? Can the same be shown for plaintext-splitting, another
idea advanced for many of the same grounds?
I think that what you are advancing is a useful idea, but I don't
think we have grounds to put very much faith in the additional
strength it will provide.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Wed, 07 Mar 2001 05:39:14 GMT
David Wagner wrote:
> ... solutions to what equation?
For input unknowns in terms of known outputs, what else?
Because the problem is underdetermined, you get multiple
solutions.
> E_k(x) = AES_0(F_k(x)),
> where F_k(x|y) = (DES_0(x) xor k) | (DES_0(y) xor k),
I *guess* that by this you mean DES_0 is repeated on the
separate subblocks of the actual input (masked_PT|new_key)
as often as required to span the whole block, e.g. 8 times
in my straw-man example.
> your mode is insecure when used with this E().
Please elaborate. AES_0 can obviously be inverted with
little work, so you must mean that the (7 independent)
pairs of DES_0(x[i/8]) xor DES_0(x[(i+1)/8]) obtained
by eliminating k are readily solved for the 8 64-bit
x[i/8] segments of the 512-bit x=(masked_PT|new_key). How?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: super strong crypto, phase 3
Date: Wed, 07 Mar 2001 05:56:25 GMT
John Savard wrote:
> you don't have always insufficient information; instead of just P1,
> you also have P2, P3, P4, ...
Yeah, but you need more than the same number of bits,
in general, for an effective solution, and the rate
at which the requisite extra information is accrued
relative to the accrual of unknowns is a constant
(apart from allowing for the one "IV"), chosen as
stipulated in my initial posting to be lower than needed
for effective cryptanalysis. I've suggested that 12.5%
fresh entropy if properly employed might be enough if
the basic block function is decent. How one determines
that is apparently not something generally known, but it
lies at the heart of the matter. I indicated in another
posting some relevant considerations for developing a
theory along these lines. From time to time I try to
get people interested in this, but perhaps it's too
daunting.
------------------------------
From: Dennis Ritchie <[EMAIL PROTECTED]>
Subject: Re: Sad news, Dr. Claude Shannon died over the weekend.
Date: Wed, 07 Mar 2001 06:21:10 +0000
"John M. Gamble" wrote:
...
> According to the NYT obit, [Shannon] suffered from Alzheimer's. So he wasn't
> much in the public eye for the last years of his life.
>
> It's a shame. From the description in the obit, he was a lively fellow.
> One wonders if anyone else ever pogo-sticked down the Bell Labs hallways?
Yes. There is still considerable liveliness, although (just like
with the famous MIT and Caltech hacks) the exploits worth remembering
happen only every so often.
I did notice one worrisome thing at a staff meeting today.
My boss, exhorting us about the need to recruit, had previously
tried to get us to find and entice a young Ken Thompson. Today he
wanted
a young Claude Shannon.
Dennis
------------------------------
Subject: Re: How good is the KeeLoq algorithm?
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Wed, 07 Mar 2001 06:32:37 GMT
"Jakob Jonsson" <[EMAIL PROTECTED]> writes:
> > "Paul Crowley" wrote ...
> > |
> > | There's an RFC that describes it, under the name "ARCFOUR".
> Search for
>
> ARCFOUR Thayer Kaukonen
>
> at Google or Altavista and you may be lucky to find any of the expired
> drafts (draft-kaukonen-cipher-arcfour-XX.txt). Yet, "ARCFOUR Algorithm" was
> never published as an RFC (if you don't believe me, check for yourself at
> ftp://ftp.isi.edu/in-notes/rfc-index.txt or
> http://www.faqs.org/rfcs/index.html).
You're absolutely right, my bad.
It must have been standardised as part of TLS, though, mustn't it?
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
Subject: Re: Any news on the KFB mode?
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Wed, 07 Mar 2001 06:32:38 GMT
Volker Hetzer <[EMAIL PROTECTED]> writes:
> However, BBS was "proven" once too and later it turned out that
> nevertheless it wasn't the perfect solution either.
You mean BBS is detectably biased? Gosh - tell me more!
thanks in advance,
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: Dave Moore <ROT13 => [EMAIL PROTECTED]>
Subject: Re: Monty Hall problem (was Re: philosophical question?)
Date: Tue, 06 Mar 2001 21:05:25 -0500
My turn to take a whack at it.
If you brute force the problem with a serious of random trials, it will
confirm that switching doors gives you a 2/3 chance of success while not
switching is 1/3.
Here's how I approach the logic:
Given three doors, your probability of picking the right one is 1/3. If I get
the other two doors, my probability is 2/3. Monty now offers you the option to
switch to my two doors or not. Easy choice. The fact that Monty shows you my
dud-door does not alter the problem.
Alternatively:
If you always switch, the only way you can lose is if you picked the right
door in the first place, which is a 1/3 chance.
Nevertheless, there's still something comforting about seeing the brute force
simulation.
PGP key available from "http://covad.net/~watcher/"
Dave Moore
------------------------------
From: "Greg Ofiesh" <[EMAIL PROTECTED]>
Subject: Re: sci.crypt?
Date: Tue, 6 Mar 2001 22:21:16 -0800
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:pqBo6.23752$[EMAIL PROTECTED]...
> Does anyone know the exact date sci.crypt was last a discussion forum
about
> "scientific cryptography"?
>
> I want to make a head stone for the group... hehehe
hehehe Really serious? hehehe
>
> Can we come to a consensus of "on topic" traffic please? I see cross
posts
> from alt.kkk, alt.2600, alt.pedophile.looky.here, etc... seriously...
>
> Tom
>
In light of the electronic voting booth that Florida wants to deploy, I
think the equipment should be a case study for this group on how flawed the
entire system really is. It would be really good to see statistics on how
unlikely someone would actually not tamper with the results in down town
central bomb shelter.
>
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: sci.crypt?
Date: 7 Mar 2001 06:47:14 GMT
Greg Ofiesh <[EMAIL PROTECTED]> wrote:
> think the equipment should be a case study for this group on how flawed the
> entire system really is. It would be really good to see statistics on how
> unlikely someone would actually not tamper with the results in down town
> central bomb shelter.
How would you gather such statistics? Seems like you'd have to detect the
tampering first...
------------------------------
From: "Lyalc" <[EMAIL PROTECTED]>
Subject: Re: PKI and Non-repudiation practicalities
Date: Wed, 7 Mar 2001 18:06:58 +1100
True, although operating support costs may theoretically be double or more,
since the legacy method can't be switched off anytime soon, at least until
the whole world comes into a steady, single state condition. Esxpecially
for payment cards.
Lyal
Anne & Lynn Wheeler wrote in message ...
>"Lyalc" <[EMAIL PROTECTED]> writes:
>
>> Yep, there is a massive phase out challenge for the migration away from
>> single DES to 3DES or AES.
>
>or public key ... the cut-over costs are effectively the same for
>single solution or multi-solution cut-over deployment. hardware token
>card with digital signatures can actually reduce various
>infrastructure costs associated with shared-secret activites (again a
>hardware token requiring a PIN is done w/o having the PIN a
>shared-secret).
>
>--
>Anne & Lynn Wheeler | [EMAIL PROTECTED] - http://www.garlic.com/~lynn/
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Cipher idea
Date: Wed, 07 Mar 2001 08:03:09 GMT
This idea is rather similar to some of Terry Ritter and Tom Denis'
ideas, but I'll post it anyway :)
t(0..15) = data being enciphered
k(0..15) = encryption key
k(i) = k(i-1)^k(i-4)^k(i-15)^k(i-16) = round keys (0 <= i < 512)
xtimes(z) = (z<<1) ^ ((z&0x80) ? (0x11b) : 0)
s(x) = sbox with LP_max <= 1/4 and DP_max <= 1/8, and no fixed points.
AES's sbox will do fine, or a random one made with Tom's sboxgen.
for r = 0..3: for i = 0..3: for j = 0..7:
(a, b) = t(FFT(i,j))
off = r*128 + i*32 + j*4
a = s(s(a^k(off+0))^k(off+1))
b = s(s(b^k(off+2))^k(off+3))
c = xtimes(a^b)
t(FFT(i,j)) = (a^c, b^c)
end for; end for; end for
Number of rounds is chosen to be >2 (to avoid mitm attacks), and as a
power of 2 (for aesthetics), giving a minimum of 4 rounds.
Key scheduling is simply an LFSR with the order 16 polynomial (0,1,4,15,
16). This means that the cipher can work with very little extra RAM;
very useful for limited memory architectures. Transforming the last 16
bytes of round key into the starting key is a linear op, and easy to
calculate. Also, for decrypting, I need to start with the last bytes,
and run the LFSR backwards; also easy to do. Of course, if you've lots
of memory, you just expand the key into a 512 byte array, and don't
worry about such silly things.
0x11b is taken from Rijndael. I see nothing about it that makes it
better than any other order 8 polynomial, except that I think it's
primitive.
LP_max is chosen for security against linear analysis:
(1/LP_max)^2x >= 256, x=2,
1/LP_max^4 >= 256,
-4 lg LP_max >= 8,
lg LP_max <= -2
LP_max <= 1/4
DP_max is chosen for security against differential analysis:
(2/DP_max)^x >= 256, x=2,
2 lg 2/DP_max >= lg 256
2 (1 - lg DP_max) >= 8
lg DP_max <= -3
DP_max <= 1/8
This makes the substitutions of a and b approximately SPRPs. I say
approximate, since it's only differential and linear analysis that
they're resistant to, not anything else. They are definitely vulnerable
to dictionary attacks and brute force. They are probably vulnerable to
related key attacks. However, since (I hope) attacking the substitution
depends on getting at it in isolation, and (I hope) this is impossible,
I'm not worried.
Can anyone suggest any theoretical (or worse, practical!) attacks?
--
The difference between theory and practice is that in theory, theory and
practice are identical, but in practice, they are not.
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
