Cryptography-Digest Digest #834, Volume #11 Mon, 22 May 00 09:13:00 EDT
Contents:
Re: Reasonably secure OTP passing (Mok-Kong Shen)
Re: Refs to "Hillclimbing" and other algorithms? (Mok-Kong Shen)
Re: Introduction to zero knowledge proofs? (Volker Hetzer)
Re: Compare 3DES's. (long) (Was: Mixmasters encrypt how?) (Mok-Kong Shen)
Re: Tired of spam! (Herbert Martin Dietze)
Re: Q: Recording on magnetic cards (Francois Grieu)
Re: Blowfish Claims ... something not right (Bohdan Tashchuk)
3DES SOURCE ("Karim A")
Re: Blowfish Claims ... something not right (Bohdan Tashchuk)
Re: pentium timings (Gisle S�lensminde)
Re: First differential attack (Mark Wooding)
Re: zeroknowledge.com and freedom.net - Snake oil?
([EMAIL PROTECTED])
Re: Cipher Contest: Whirl128 (paper) (Runu Knips)
Re: Blowfish Claims ... something not right (Mark Wooding)
Re: Equivalent keys in WHIRL128 (Runu Knips)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Reasonably secure OTP passing
Date: Mon, 22 May 2000 09:59:49 +0200
John Savard wrote:
> This still avoids some of the attacks available on
> Playfair+transposition or transposition+Playfair. So what we have is
> the concept that unkeyed 'scrambling' steps - like what modems do to
> avoid a long string of 0 bits becoming a signal that doesn't clock -
> can improve the strength of some cipher methods.
I tend to think that unkeyed scrambling has only a marginal effect, if
at all. Any preprocessing should involve key (secret material) in my
humble opinion.This is what underlies whitening, if I don't err. The
text materials (books etc.) in the scheme I mentioned are to be
encrypted by algorithms (maybe not necessarily very strong) with
secret keys. These keys are in effect 'extending' in some measure
the key of the algorithm you suggested to encrypt the result obtained
by OTP encryption (OTP-like encryption in the scheme I mentioned.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Refs to "Hillclimbing" and other algorithms?
Date: Mon, 22 May 2000 10:09:58 +0200
Sundial Services wrote:
> Where can I find URLs and sample-code which refer to "Hillclimbing" and
> other computer techniques relevant to cryptanalysis?
>
> (I presume that many of them exist by now.)
I don't have that impression. Hillclimbing in cryptanalysis appears to
be a method due to Jim Gillogry. He explained a little bit of it in our
group but not to the extent for the uninitiated to be able to practice
that method in my humble opinion.
M. K. Shen
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Introduction to zero knowledge proofs?
Date: Mon, 22 May 2000 08:02:35 +0000
Thanks a lot!
Greetings!
Volker
--
"Isn't it just my luck. Some stranger says to me, "I LOVE YOU"
and next thing I know, I've got this virus..."
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Compare 3DES's. (long) (Was: Mixmasters encrypt how?)
Date: Mon, 22 May 2000 10:32:30 +0200
Paul Schlyter wrote:
> William Rowden <[EMAIL PROTECTED]> wrote:
>
> > . If EDE is preferred due to backwards compatibility only, why would
> > one use it (as in Mixmaster) with 24 bytes of key? Obviously, here 24
> > bytes * 8 bits/byte = 192 bits = 3 keys * (56 bits + 8 parity
> > bits)/key. That is, why use E(K1,D(K2,E(K3,x))) rather than
> > E(K1,E(K2,E(K3,x)))?
>
> If K1, K2 and K3 are all different, there are ways to attack 3DES
> which effectively reduces the key space to a 16-byte key. Therefore
> using K1 different from K3 offers little security advantages over
> using K1=K3.
But presumably not in the case E(K1,E(K2,E(K3,x)))? If one also
applies chaining and variable keys, I could barely imagine any
probability of the scheme being broken in foreseeable future in
practice.
M. K. Shen
------------------------------
From: Herbert Martin Dietze <[EMAIL PROTECTED]>
Subject: Re: Tired of spam!
Date: Mon, 22 May 2000 07:45:58 GMT
[EMAIL PROTECTED] wrote:
> Never use your main e-mail when you surf the newsgroups: You might get spammed.
... so he writes and spams dozens of NGs.
*plonk*
Herbert
--
Borgasm: The ecstacy of being assimilated.
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: Q: Recording on magnetic cards
Date: Mon, 22 May 2000 10:34:01 +0200
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> Except the part covered by the black stripe, which I couldn't look
> through, there was no indication of presence of a chip.
Strange. I am unaware of any tehnology that can read (much less write)
a magnetic stripe at more than 0.1 mm distance. And the only
technologies I know that can read and write more than a few bits
into a card at a distance all use an IC in the card.
> One acts normally in economical ways. What isn't needed is not done.
> Why should the designer take the trouble to hide the chip?
When manufacturing a contactless IC card, the most economical process
is to assemble the IC and coil, then laminate these between two plastic
foils. This, as a side effect, hides the IC. It is more costly to
manufacture a contactless IC card that also has contacts : the contacts
have a cost, they need to be precisely located, and it is hard to have
then go thru one side of the card.
BTW, even in contact IC cards, the IC is hidden behind the metal that is
between the contacts.
Francois Grieu
------------------------------
From: Bohdan Tashchuk <[EMAIL PROTECTED]>
Subject: Re: Blowfish Claims ... something not right
Date: Mon, 22 May 2000 01:40:59 -0700
Paul Rubin wrote:
>
> >8 cycles a byte with blowfish? That's hard to believe, mainly
> >because the look ups in the F function would be a source of
> >bottleneck.
>
> Wait a sec, I must have meant 8 cycles per *round*. This is coming
> back to me. That would be 16 cycles/byte.
The value of 16 cycles/byte corresponds closely to the performance claim by
Schneier et all in the book they wrote called
The Twofish Encryption Algorithm
ISBN 0-471-35381-7.
They give a lot of different values for various options of pre-computing
keys, various number of plaintext bytes, ASM versus C, etc. As an
asymptotic case see:
Table 5.3. Best Speed to Encrypt a Message
with a New 128-bit Key on a Pentium Pro
They claim:
for 1 Megabyte of plaintext
Total Clocks per Byte is 16.1
The key setup time isn't too bad, because:
for 1 Kilobyte of plaintext
Total Clocks per Byte is 24.5
Put another way, an 800 MHz P3 processor is capable of encrypting at
roughly 50 Megabytes per second, which is pretty darn good IMHO.
------------------------------
From: "Karim A" <[EMAIL PROTECTED]>
Subject: 3DES SOURCE
Date: Mon, 22 May 2000 10:51:45 +0200
Reply-To: "Karim A" <[EMAIL PROTECTED]>
Hi all,
Where can I find source code of Triple DES encryption ?
Thanks,
Karim
------------------------------
From: Bohdan Tashchuk <[EMAIL PROTECTED]>
Subject: Re: Blowfish Claims ... something not right
Date: Mon, 22 May 2000 02:01:15 -0700
Paul Rubin wrote:
>
> >8 cycles a byte with blowfish? That's hard to believe, mainly
> >because the look ups in the F function would be a source of
> >bottleneck.
>
> Wait a sec, I must have meant 8 cycles per *round*. This is coming
> back to me. That would be 16 cycles/byte.
The value of 16 cycles/byte is a little better than the performance claim
by Schneier et all in the book they wrote called
The Twofish Encryption Algorithm
ISBN 0-471-35381-7.
But since the book was written a year or two ago, they may have improved
their algorithm in the meantime. In the book in Table 10.1 they claim that
Blowfish runs at 19.8 clocks/byte on a Pentium. The Counterpane web page
(presumably more recent than the book) that was referenced at the start of
this thread claims 18 clocks/byte on a Pentium.
More interesting to me is Twofish, since it has twice the ley length and is
faster. In the book they give a lot of different values for various options
of pre-computing keys, various number of plaintext bytes, ASM versus C,
etc. As an asymptotic case see:
Table 5.3. Best Speed to Encrypt a Message
with a New 128-bit Key on a Pentium Pro
They claim:
for 1 Megabyte of plaintext
Total Clocks per Byte is 16.1
The key setup time isn't too bad, because:
for 1 Kilobyte of plaintext
Total Clocks per Byte is 24.5
Put another way, an 800 MHz P3 processor is capable of encrypting Twofish
at roughly 50 Megabytes per second, which is pretty darn good IMHO.
------------------------------
From: [EMAIL PROTECTED] (Gisle S�lensminde)
Subject: Re: pentium timings
Date: 22 May 2000 12:01:33 +0200
In article <[EMAIL PROTECTED]>, Mok-Kong Shen wrote:
>
>
>tomstd wrote:
>
>> Anyone interested in timing their code in cycles on a pentium
>> class computer (i.e k6, 586, ppro, MII, etc...) can use the code
>> I developped (well it's not my idea, I just put it together
>> nicely) here
>
>A question of curiosity: How do you get the time to sufficient accuracy?
>On a computer, e.g. PC, there are other tasks running concurrently.
I haven't tried Tom's code, but most operation systems runs each thread
for slices of 10-100 ms at a time. On a 100 MHz computer with 10 ms time
slices, that is 1_000_000 cycles, which means that the probability of a context
swich in the middle is small if you measure ciphers, which in most cases runs
on less than 1000 cycles.
I have observed context swiches in timings, but that's very rare. You will
recognise a context swich as a way to high cycle count. If you run the test
several times you are safe.
--
Gisle S�lensminde ( [EMAIL PROTECTED] )
ln -s /dev/null ~/.netscape/cookies
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: First differential attack
Date: 22 May 2000 10:17:48 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> And thru all 16 rounds is about 2^-36 or (2^-9^(8/2)). If I did
> this right, it will require 2^37 pairs to break...
I thought you had 16 rounds. Now, I agree that the first two rounds can
be skipped by choosing b = b' (mod 257) and a = a', but that leaves 14
rounds. The third round inputs will be (c, d), (c, d') for some c, d,
d'. We have d = d' (mod 257) with probability approximately 1/257
(the bias is small, because 2^32 = 1 (mod 257)). So at this point we
have an iterative 2-round characteristic with probability 1/257, which
we can apply to (say) 12 rounds and follow with 2R attack. So we get a
right pair with probability 257^-6, which is 2^48-ish. I think you're
over-pessimistic.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: zeroknowledge.com and freedom.net - Snake oil?
Date: Mon, 22 May 2000 10:36:35 GMT
In article <8g0bua$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Guy Macon) wrote:
> In article <8fu21q$shb$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
muenchen.de
> wrote:
> >
> >In article <8ftn5f$[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] (Guy Macon) wrote:
> >>...
> >> >Sure this point is the catchiest point. Anonymizers rewrite URLs,
> >> >but therefore they work behind firewalls!
> >>
> >> If the users of the firewall I administer want to use either of
> >> your products and I don't want them to, I can stop them. (in real
> >> life I would offer free tech support!). Your system doen't change
> >> this.
> >
> >And if I don't want that the users don't use ZKS I can stop them
> >too. Now what?
>
> Uh, Alex? Did you notice that I said "EITHER of your products"?
Ah, now I see it ...
> >NO System can change that, but Web-Anonymizers work behind firewalls
> >(until the admin restricts it) Proxy-based Servers as ZKS don't.
>
> Think of it from my standpoint as a firewall admin. I block site X.
> Now why did I do such a thing? Because my monitoring software says
> that site X has content that I don't want my users to access. Will
> not my monitoring software come to the same conclusion about your
> anonymizer as soon as that user accesses the content of site X?
Depends which anonymizer is used. If there would be a SSL-connection
you would only see that the anonymizer-server is accessed, but you
won't know the url and the content. So you don't know what the
anonymizer-user is doing.
> (In the real world I would set the firewall to let users use either
> of your products, but that's because I am in the business of
> protecting users from attackers, not filtering or blocking them)
I don't know were you are working, but all firewall-systems I've
seen till now, don't allow connection from outside to inside AND
insode to outside. They have to use a web-proxy to access pages outside.
Why? Because first they should work and don't do other things and
second attacks can also be started from inside (like Netbus, Back
Orifice and other Trojan Horses, Viruses, ...)
GreetingX,
Alex - http://anonymouse.is4u.de/
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Mon, 22 May 2000 13:43:28 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Cipher Contest: Whirl128 (paper)
tomstd wrote:
> <snip>
> ---
> The avalanche addition has been seen in SHA-1. The main
> inspiration for using this was however an dispute between me and
> Tom St Denis on news:sci.crypt, where Tom called another loop in
> a hash function designed by him an 'avalanche addition', which
> it wasn't.
> ---
>
> When exactly did I make any mention to avalanche addition?
>
> Tom
Well, I don't remeber the exact date, and I didn't logged the dispute
itself,
but it was in your hash function, where I simplified your 'avalanche
addition'
(the #if 0 below) to something far easier (the #else below):
==============================================================================
#include <stdio.h>
/* three permutation polynomials */
#define F(x) (0x9E37B197ul + (255*x) + (4095*x*x) + (127*x*x*x) +
(8191*x*x*x*x) + (65535*x*x*x*x*x))
#define G(x) (0x513FA971ul + (17*x) + (31*x*x) + (511*x*x*x) +
(1023*x*x*x*x) + (32767*x*x*x*x*x))
#define H(x) (0xb7e14aeful + (511*x) + (15*x*x) + (2047*x*x*x) +
(31*x*x*x*x) + (63*x*x*x*x*x))
/* rotate code */
#define ROL(x, n) ((x<<(n&31))|(x>>(32-(n&31))))
#define ROUNDS 20
#define SIZE (6 * ROUNDS)
/* compresses a 16-word (64 byte) input to a 6-word (24 byte) output */
void hash(unsigned long *in, unsigned long *res)
{
unsigned long temp[SIZE], t, a, b, c, d, e, f;
int r;
/* stretch the input */
memcpy(temp, in, sizeof(long) * 16);
#if 0
for (r = 16; r < SIZE; r++) {
t = temp[r - 16] ^ temp[r - 15] ^ temp[r - 14] ^ temp[r - 13] ^
temp[r - 11] ^ temp[r - 7] ^ temp[r - 6] ^ temp[r - 3] ^
temp[r - 2] ^ temp[r - 1] ^ 0x9E37B91Ful ^ r;
temp[r] = ROL(t, 11);
}
#else
t = 0x9E37B91Ful;
for (r = 0; r < 15; ++r)
t ^= temp[r];
for (r = 16; r < SIZE; ++r) {
t ^= temp[r-1];
temp[r] = ROL(t ^ r, 11);
t ^= temp[r-16];
}
#endif
/* load registers */
a = res[0]; b = res[1]; c = res[2]; d = res[3]; e = res[4]; f = res[5];
/* rounds */
for (r = 0; r < ROUNDS; r++) {
a ^= (t = F(d) ^ G(e) ^ H(f)) + temp[6*r+0]; t >>= 27ul; a = ROL(a,
t);
b ^= (t = F(e) ^ G(f) ^ H(d)) + temp[6*r+1]; t >>= 27ul; b = ROL(b,
t);
c ^= (t = F(f) ^ G(d) ^ H(e)) + temp[6*r+2]; t >>= 27ul; c = ROL(c,
t);
d ^= (t = F(a) ^ G(b) ^ H(c)) + temp[6*r+3]; t >>= 27ul; d = ROL(d,
t);
e ^= (t = F(b) ^ G(c) ^ H(a)) + temp[6*r+4]; t >>= 27ul; e = ROL(e,
t);
f ^= (t = F(c) ^ G(a) ^ H(b)) + temp[6*r+5]; t >>= 27ul; f = ROL(f,
t);
}
/* store */
res[0] = a; res[1] = b; res[2] = c; res[3] = d; res[4] = e; res[5] = f;
}
void main(void)
{
unsigned char buf[64];
unsigned long *in=(unsigned long*)buf, out[6];
do {
memset(buf, 0, sizeof(buf));
gets(buf);
if (strlen(buf) > 1) {
out[0] = 0x12345678; out[1] = 0x9ABCDEF1; out[2] = 0x23456789;
out[3] = 0xABCDEF12; out[4] = 0x3456789A; out[5] = 0xBCDEF123;
hash(in, out);
printf("%08lx%08lx%08lx%08lx%08lx%08lx\n", out[0], out[1],
out[2],
out[3], out[4], out[5]);
}
} while (strlen(buf) > 1);
}
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Blowfish Claims ... something not right
Date: 22 May 2000 12:05:49 GMT
Bohdan Tashchuk <[EMAIL PROTECTED]> wrote:
> More interesting to me [than Blowfish] is Twofish, since it has twice
> the ley length
Maximum Twofish key size is 256 bits. Maximum Blowfish key size is 448
bits. Which is twice the length of the other?
Fiddling with the Twofish key schedule is tricky. I suppose that more
q0/q1 permutations could be strapped onto the h-function, if you were
careful about doing it right. q0-q1-q1-q0 on the top would give an
extra 64 bits of key[1]; then we've run out of S-box patterns[2] with
320 bits of key. Would repeating the sequence of patterns be a security
problem?
[1] Although note that in all the existing stages of h, we change two
q-boxes and leave the other two alone. Putting q0-q1-q1-q0 at the
top would change all four. Is this a problem? I don't know.
[2] Well, patterns with exactly two q0s and two q1s.
-- [mdw]
------------------------------
Date: Mon, 22 May 2000 14:09:30 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Equivalent keys in WHIRL128
David Eppstein wrote:
> Whirl128 is a block cipher submitted to the sci.crypt cipher contest by
> Runu Knip; see http://www.wizard.net/~echo/crypto-contest.html for details.
>
> I have some concerns with the subkey generation phase of the algorithm,
> specifically this loop:
>
> *------------------------------------------------------------------*
> | for j in [1..4] do |
> | for i in [0..63] do |
> | K[i] := K[i] + 0xb7e15161 |
> | + (K[(i+ 3) mod 64] <<< K[i] shr 10) |
> | + (K[(i+13) mod 64] <<< K[i] shr 25) |
> | + (K[(i+32) mod 64] <<< K[i] shr 0) |
> | + (K[(i+41) mod 64] <<< K[i] shr 15) |
> | + (K[(i+57) mod 64] <<< K[i] shr 5) |
> | + (K[(i+62) mod 64] <<< K[i] shr 25); |
> *------------------------------------------------------------------*
>
> Here K is initialized to the key data (D) and padded with zeros. But the
> problem is that multiple values of D can lead to the same final value of
> K. For instance, if D is a 128 bit key (the minimum recommended for the
> algorithm) consisting of the 4 words (0x55555555 - 0xb7e15161, *, *,
> 0x55555555) and
> D' = (0xaaaaaaaa - 0xb7e15161, *, *, 0x55555555), then the very first
> iteration of the loop will set K[0]=0xffffffff in both cases, after which
> those two keys act completely the same.
>
> I was too lazy to work out the details of which key is mapped to which,
> but I did a heuristic analysis based on the assumption that, if the K[i]'s
> involved are random, the data-dependent rotation plus addition involved at
> each iteration of the loop acts like a random function. Then, I think,
> for a given 128-bit key (p,q,r,s), the expected number of equivalent keys
> (p',q,r,s) such that K[0] becomes the same after the first iteration (as
> in the example) is almost one (more precisely 31/32 since the values p'
> with the same rotation amount as p certainly don't work and each remaining
> value has a 2^{-32} chance of working). The second iteration of the loop
> can't do anything interesting (all the other K[j]'s are still zero) but in
> the third iteration we add a shifted copy of K[0] to K[2], so have an
> expectation of almost one equivalent key (p,q,r',s) such that the K arrays
> become the same in the third iteration. And similarly, we have an
> expectation of almost one equivalent key (p,q,r,s') such that the K arrays
> become the same in the fourth iteration.
>
> Moreover, there are various possibilities for combining pieces from these
> equivalent keys. If p' and r' both exist, then (p',q,r',s) is also an
> equivalent key, since K[0] becomes the same on the first iteration after
> which the third iteration looks exactly like the third iteration for
> (p,q,r',s). If r' and s' both exist, then (p,q,r',s') is also an
> equivalent key since r' and s' don't interact with each other until much
> later in the subkey generation phase.
>
> Finally, if s' exists, then there is an expectation of almost one for
> there to exist a value p* such that the first iteration for (p*,q,r,s')
> makes K[0] the same as the first iteration for (p,q,r,s). If so, then
> (p*,q,r,s') is also an equivalent key, as is (p*,q,r',s').
>
> With all these equivalent keys, if one could quickly identify one member
> of each equivalence class, the cost of brute force searching should go
> down from 2^128 to something smaller like maybe 2^125.
I.e., according to our definition, Whirl128 is broken. Congratulations
!!!
I'm really surprised that the key schedule had the error :)
> Roughly the same analysis would work for key lengths larger than 128 bits
> and the savings would be greater since there seems to be more chances for
> keys to become equivalent.
>
> A patch is easy: simply make sure that each step of the subkey generation
> stage is invertible. For instance, change the line
> K[i] := K[i] + ...
> to
> K[(i+1)&077] += ...
> but leave unchanged all the other occurrences of K[i] in the expression,
> so that part of the key is acting on other parts of the key (like a
> Feistel cipher) rather than on itself.
Thank you very much. I think that changing the rotations to fixed
offsets,
like I've already done at home for some other reason, leads also to an
invertible operation (The other reason was, that one cannot be sure if
every bit influences all lower bits of the array if I rotate just by
'random' values).
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
