Cryptography-Digest Digest #394, Volume #14 Sun, 20 May 01 07:13:00 EDT
Contents:
Re: What about SDD? (David Wagner)
Key Generation (William Ahern)
Single-cycle sbox question (Benjamin Goldberg)
Re: TC15a cryptanalysis ("Scott Fluhrer")
Re: Comparing two encrypted numbers (David Wagner)
Re: Single-cycle sbox question (SCOTT19U.ZIP_GUY)
Re: Single-cycle sbox question (Bryan Olson)
Re: TC15a cryptanalysis ("Tom St Denis")
Re: Single-cycle sbox question ("Henrick Hellstr�m")
Re: Single-cycle sbox question ("Tom St Denis")
TC15a SAC Analysis ("Tom St Denis")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: What about SDD?
Date: 20 May 2001 02:49:07 GMT
Harris Georgiou wrote:
>Given the exponentially
>growing capacity in storage and communications over time, I think gives a
>whole new area of interest in secure storage and exchange of sensitive data.
>Using certification and authentication techniques, or huge PRNG-based
>distributions, it is possible to ensure confidentiality by means of
>information distribution (SDD) rather than hiding (stego) or sealing
>(crypto).
That sounds like a pretty persuasive argument. Yes, I believe
that in the radiocommunications world, there are well-known techniques
for using information dispersal to conceal information. A simple
version goes like this: At time t, use the t-th output of a keystream
generator to pick an unpredictable frequency f_t, and transmit the t-th
chunk of data on f_t. Probably one would want to pre-encrypt the data
for best assurance of confidentiality.
One benefit this technique provides is low probability of intercept.
An attacker who cannot predict the keystream generator output is in a
very difficult position: she cannot follow the frequency hops; storing
data from all possible frequency slots at each possible time position
for later analysis is very expensive (if there are enough frequency
slots); and even if one could do this, there are exponentially many
possible ways to piece together the data samples.
Another benefit this provides is resistance to jamming. Although I
don't know much about radiofrequency engineering, it would appear on
the surface that an attacker who cannot predict the keystream generator
must transmit at high power on a large fraction of the possible
frequency slots to have a reasonable chance of preventing the message
from getting through, and this seems likely to be expensive if the
number of frequency slots is much larger than typical message lengths.
I believe this technique, and others like it, are described a little
bit in Ross Anderson's excellent textbook, _Security Engineering_.
Note that I am not an expert in this area, so I might have gotten some
of the details above wrong, but I believe the sense of it is probably
roughly correct.
It is not quite as clear how to apply this to, say, Internet
communications, but maybe there is something that could be done.
For instance, if there is sufficient diversity in the routes available
on the net, one could try to send each packet on a different route,
selected randomly using a keystream generator (note that in this
case, the receiver need not know the key the sender uses); this
would appear to raise the cost of certain classes of eavesdropping
attacks. If you've already got cryptographic protection of your
Internet communications, I'm not sure whether there's much value
in such an approach (although maybe it helps to increase the cost
of traffic analysis?), but if for some reason crypto is hard to deploy,
this approach might serve as a partial measure to help manage the
risk of eavesdropping for such communications.
------------------------------
From: [EMAIL PROTECTED] (William Ahern)
Subject: Key Generation
Date: 19 May 2001 21:15:31 -0700
I am trying to get 3 pieces of secret, shared data from a DH key
exchange:
1) 16 byte cipher key
2) 16 byte hmac key
3) 2 byte random sequence number (from which to being packet
sequencing)
One end transmits p, g, k and a random seed, the other
returns k' (wrong symbols?).
Both ends then use the computed DH shared secret and the seed value
as input into a PRF (below). They they use the output of the PRF to
get the cipher key, hmac key and the sequence number.
Is this a bad design (absent authentication/key signing)?
This is used in a protocol I'm developing to implement
a PipeNet (see http://www.eskimo.com/~weidai/pipenet.txt)
--
>From TLS 1.0 Draft RFC (absent the MD5/SHA1 split; just SHA1)
PRF(secret, seed) = HMAC_hash(secret, A(1) + seed) +
HMAC_hash(secret, A(2) + seed) +
HMAC_hash(secret, A(3) + seed) + ...
Where + indicates concatenation.
A() is defined as:
A(0) = seed
A(i) = HMAC_hash(secret, A(i-1))
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Single-cycle sbox question
Date: Sun, 20 May 2001 00:22:16 -0400
I know of two methods for generating a single-cycle sbox.
The first one is:
do { sbox = random_permutation } until( single_cycle(sbox) );
The second one is:
temp = random_permutation
for( i = 0 to N-2 ) {
sbox[ temp[i] ] = sbox[ temp[i+1] ];
sbox[ temp[N-1] ] = sbox[ temp[0] ];
Now, while I know that method two is of course much, much, faster than
method one, I *don't* know whether or not it can produce all possible
single-cycle sboxes, or whether it is biased. I don't *think* it's
biased, but I'm not sure...
Tom's sboxgen uses method 1. I plan on making a change in my own copy
to use method 2, but I want to first know that it will be correct.
--
Customer: "I would like to try on that suit in the window."
Salesman: "Sorry sir, you will have to use the dressing room."
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: TC15a cryptanalysis
Date: Sat, 19 May 2001 21:09:47 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:YlDN6.139133$[EMAIL PROTECTED]...
>
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> news:9e6v68$tqj$[EMAIL PROTECTED]...
> >
> > Actually, during my tests, I averaged over 100 different sets of random
> > subkeys. In addition, because of the structure of TC15A, I'd expect the
> > same sort of biases to exist essentially independent of the keys -- all
> you
> > do with the subkeys is xor them into the block periodically, and if we
use
> > random starting blocks, xoring in unknown random subkeys should have
> little
> > effect, at least to a first approximation. Of course, if you've
observed
> > that different keys do behave differently, then ignore that argument.
>
> I agree my point is that I think the window is too small to get a good
idea
> of a useful bias. If you could show mathematically why the bias works
that
> would be more useful.
Actually, a bias like I observed can be exploited even if we don't have the
foggiest notion *why* it works. However, I originally suspected (and looked
for) a SAC weakness because the cipher doesn't try to difuse very hard, and
what difusion is there is rather chaotic. The only things that will defuse
anything between columns are:
- The rotates by 1, 9 and 17
- The multiplies by 3 and 9
- The carries internal to the addition.
All this difusion is directed upwards, and if you (for example) you have a
differential in column 13, then it'll take a number of the above steps to
difuse to column 12. In addition, all the difusion happens on a bitwise
basis, and that makes those paths unreliable -- if there is a path of (say)
5 steps from column 13 to column 12, then with probability 1-2^{-5}, one of
the bits it relies on may just happen to have a zero differential, and so
that path will not influence the output bit. If that happens a nontrivial
amount of the time to all the paths from the input to the output, then the
output bit will be biased towards a zero differential.
Another idea for an attack: look at differentials that start with a
differential at bit 14 of C and bit 31 of D. Then, with probability 0.25,
the output differential of the first round will consist of bit 31 of D
(assuming I've done the math right -- I haven't bothered testing this).
This effectively wacks off another round of the cipher, at the cost of /4
output bias (and hence, 16x more chosen plaintexts going in)
--
scott
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Comparing two encrypted numbers
Date: 20 May 2001 05:28:51 GMT
David Wagner wrote:
>Martin Schweitzer wrote:
>>From what I understood (which was brief, second hand and via an e-mail),
>>this algorithm (or it could have been a protocol) allowed to numbers to be
>>compared to see which was greater.
>
>Well, one can say that a secure non-interactive protocol for this
>is unlikely to exist, because binary search would then suffice to
>reveal all of the encrypted data [...]
Oops. To be more precise, what I meant is that it's not possible
to do this in general without authorization or consent from either
the sender or receiver, because then binary search is a risk.
However, one thing that a sender *can* do, if the sender wants to
authorize a comparison between a specified pair of encryptions,
is that the sender can include a non-interactive zero-knowledge
proof of which is larger. This proof may later be verified without
communication with the sender. Similarly, after the receiver
decrypts the pair of ciphertexts, she too can broadcast a non-interactive
zero-knowledge proof that can later be verified offline. Of course,
both of these scenarios require authorization from one of the two
parties; we've simply shifted when they give the authorization earlier
in time, so that interaction is not required.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Single-cycle sbox question
Date: 20 May 2001 05:40:05 GMT
[EMAIL PROTECTED] (Benjamin Goldberg) wrote in
<[EMAIL PROTECTED]>:
>I know of two methods for generating a single-cycle sbox.
>
>The first one is:
>
>do { sbox = random_permutation } until( single_cycle(sbox) );
>
>The second one is:
>
>temp = random_permutation
>for( i = 0 to N-2 ) {
> sbox[ temp[i] ] = sbox[ temp[i+1] ];
>sbox[ temp[N-1] ] = sbox[ temp[0] ];
>
>Now, while I know that method two is of course much, much, faster than
>method one, I *don't* know whether or not it can produce all possible
>single-cycle sboxes, or whether it is biased. I don't *think* it's
>biased, but I'm not sure...
>
>Tom's sboxgen uses method 1. I plan on making a change in my own copy
>to use method 2, but I want to first know that it will be correct.
>
I suppose your method two is like what I use in scott16u or scott19u
I have at one time or the other showed or had software to allow any
single cycle sbox to be created. If you look at source code you can
see how its done. SInce this is what I have to do in my code.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Single-cycle sbox question
Date: Sun, 20 May 2001 01:02:14 -0700
Benjamin Goldberg wrote:
>
> I know of two methods for generating a single-cycle sbox.
There are others; the efficient ones of which I know can
be viewed as cases of the theorem:
For any single-cycle permutation c(x) on set S,
if P(x) is selected at random from the uniform
distribution of all permutations on S, then
P(c(P^-1(x))) is uniformly distributed over all
single-cycle permutations on S.
> The second one is:
>
> temp = random_permutation
> for( i = 0 to N-2 ) {
> sbox[ temp[i] ] = sbox[ temp[i+1] ];
> sbox[ temp[N-1] ] = sbox[ temp[0] ];
I think the line in the body of the for loop should be:
sbox[temp[i]] = temp[i+1];
> Now, while I know that method two is of course much, much, faster than
> method one, I *don't* know whether or not it can produce all possible
> single-cycle sboxes, or whether it is biased. I don't *think* it's
> biased, but I'm not sure...
Given the code correction, this is a case of the theorem,
where the given single-cycle permutation c is
c(i) = i+1 mod N
Equivalently, c = (1, 2, 3, ... N-2, N-1, 0).
--Bryan
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: TC15a cryptanalysis
Date: Sun, 20 May 2001 10:11:26 GMT
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:9e7gqb$pqb$[EMAIL PROTECTED]...
>
> Tom St Denis <[EMAIL PROTECTED]> wrote in message
> news:YlDN6.139133$[EMAIL PROTECTED]...
> >
> > "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> > news:9e6v68$tqj$[EMAIL PROTECTED]...
> > >
> > > Actually, during my tests, I averaged over 100 different sets of
random
> > > subkeys. In addition, because of the structure of TC15A, I'd expect
the
> > > same sort of biases to exist essentially independent of the keys --
all
> > you
> > > do with the subkeys is xor them into the block periodically, and if we
> use
> > > random starting blocks, xoring in unknown random subkeys should have
> > little
> > > effect, at least to a first approximation. Of course, if you've
> observed
> > > that different keys do behave differently, then ignore that argument.
> >
> > I agree my point is that I think the window is too small to get a good
> idea
> > of a useful bias. If you could show mathematically why the bias works
> that
> > would be more useful.
>
> Actually, a bias like I observed can be exploited even if we don't have
the
> foggiest notion *why* it works. However, I originally suspected (and
looked
> for) a SAC weakness because the cipher doesn't try to difuse very hard,
and
> what difusion is there is rather chaotic. The only things that will
defuse
> anything between columns are:
>
> - The rotates by 1, 9 and 17
> - The multiplies by 3 and 9
> - The carries internal to the addition.
>
> All this difusion is directed upwards, and if you (for example) you have a
> differential in column 13, then it'll take a number of the above steps to
> difuse to column 12. In addition, all the difusion happens on a bitwise
> basis, and that makes those paths unreliable -- if there is a path of
(say)
> 5 steps from column 13 to column 12, then with probability 1-2^{-5}, one
of
> the bits it relies on may just happen to have a zero differential, and so
> that path will not influence the output bit. If that happens a nontrivial
> amount of the time to all the paths from the input to the output, then the
> output bit will be biased towards a zero differential.
This is not entirely true. Remember that there is a sbox going across the
words. So bits 1,41,81,96 are going into the first sbox etc. So in the
next round when C is rotated 17 the bits mixed will go below bit 17.
> Another idea for an attack: look at differentials that start with a
> differential at bit 14 of C and bit 31 of D. Then, with probability 0.25,
> the output differential of the first round will consist of bit 31 of D
> (assuming I've done the math right -- I haven't bothered testing this).
> This effectively wacks off another round of the cipher, at the cost of /4
> output bias (and hence, 16x more chosen plaintexts going in)
I still want to know if your SAC bias is correct. I haven't been able to
confirm that it exists.
Tom
------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: Single-cycle sbox question
Date: Sun, 20 May 2001 12:13:23 +0200
See http://www.streamsec.com/createsc.asp The proof is incuded. I suppose
that's where you got the idea in the first place.
If you are using key data to create the permutation and want to avoid key
collisions, you should use the algorithm at our homepage. Otherwise you
would obtain each permutation n times, where n is the length of the
permutation. Consequently:
temp := a permutation of length n-1.
J := n-1;
for I := 0 to n-2 do begin
X := temp[I];
SBox[J] := X;
J := X;
end;
SBox[J] := n-1;
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
"Benjamin Goldberg" <[EMAIL PROTECTED]> skrev i meddelandet
news:[EMAIL PROTECTED]...
> I know of two methods for generating a single-cycle sbox.
>
> The first one is:
>
> do { sbox = random_permutation } until( single_cycle(sbox) );
>
> The second one is:
>
> temp = random_permutation
> for( i = 0 to N-2 ) {
> sbox[ temp[i] ] = sbox[ temp[i+1] ];
> sbox[ temp[N-1] ] = sbox[ temp[0] ];
>
> Now, while I know that method two is of course much, much, faster than
> method one, I *don't* know whether or not it can produce all possible
> single-cycle sboxes, or whether it is biased. I don't *think* it's
> biased, but I'm not sure...
>
> Tom's sboxgen uses method 1. I plan on making a change in my own copy
> to use method 2, but I want to first know that it will be correct.
>
> --
> Customer: "I would like to try on that suit in the window."
> Salesman: "Sorry sir, you will have to use the dressing room."
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Single-cycle sbox question
Date: Sun, 20 May 2001 10:13:47 GMT
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I know of two methods for generating a single-cycle sbox.
>
> The first one is:
>
> do { sbox = random_permutation } until( single_cycle(sbox) );
>
> The second one is:
>
> temp = random_permutation
> for( i = 0 to N-2 ) {
> sbox[ temp[i] ] = sbox[ temp[i+1] ];
> sbox[ temp[N-1] ] = sbox[ temp[0] ];
>
> Now, while I know that method two is of course much, much, faster than
> method one, I *don't* know whether or not it can produce all possible
> single-cycle sboxes, or whether it is biased. I don't *think* it's
> biased, but I'm not sure...
>
> Tom's sboxgen uses method 1. I plan on making a change in my own copy
> to use method 2, but I want to first know that it will be correct.
Well you can always list a single cycle as (x y z) for example (3 2 1) which
means 1 => 3, 3 => 2, 2 => 1, so the table would be { 3, 1, 2 }
Just make a random sbox, then find the entries and see the next element.
I.e search for 1 first, then 2, then 3... etc..
Not too hard.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: TC15a SAC Analysis
Date: Sun, 20 May 2001 10:32:02 GMT
Scott was onto the right track despite his numbers being wrong.
In two independent trials I got some SAC biases in common namely
4 => 3, -3780, 0.496395
58 => 0, -5026, 0.495207
89 => 0, -6846, 0.493471
89 => 3, -8232, 0.492149
Note that between the two trials these didn't have the same prob, they were
just listed as the highest. Bit 58 is really bit 26 of B, bit 89 is really
bit 25 of D.
I am doing another SAC test to see if it agrees.
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
** 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
******************************
