Cryptography-Digest Digest #181, Volume #13 Sat, 18 Nov 00 13:13:00 EST
Contents:
Re: DES question: Has this ever been proven before? (Raphael Phan)
Re: DES question: Has this ever been proven before? (Raphael Phan)
Re: Rijndael: Impossible differential cryptanalysis on 5 rounds (Raphael Phan)
Re: Rijndael: Impossible differential cryptanalysis on 5 rounds (Raphael Phan)
Re: help on user authentication protocol (Thomas Wu)
Re: Q: fast block ciphers (Simon Johnson)
Re: [Question] Generation of random keys (Simon Johnson)
Re: MUST READ IN ORDER TO UNDERSTAND ASTROLOGICAL ORIGINS (Ichinin)
Cryptogram Newsletter is off the wall? (Tom St Denis)
Re: Hitachi - on what grounds ?? (John Savard)
Re: Integer encoding on a stream (Mikael Lundqvist)
Re: Book recommendation, please (David A Molnar)
Enigma development (Richard Heathfield)
Re: Book recommendation, please (David A Molnar)
Re: Cryptogram Newsletter is off the wall? (Bruce Schneier)
Re: Hitachi - on what grounds ?? (Terry Ritter)
Re: Cryptogram Newsletter is off the wall? ([EMAIL PROTECTED])
Re: Hitachi - on what grounds ?? (John Savard)
----------------------------------------------------------------------------
From: Raphael Phan <[EMAIL PROTECTED]>
Subject: Re: DES question: Has this ever been proven before?
Date: Sat, 18 Nov 2000 06:30:01 GMT
So you are saying that such a situation would exist? I was wondering
about this because if you consider that you have an input xor never
ever causing an output xor of the same value, then the complexity of
Knudsen's impossible differential attack on DEAL would be reduced. But
I guess so such situation exists...
Thank you all for your replies..
Raphael
In article <8v3rb9$56i$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David Wagner) wrote:
> Paul Crowley wrote:
> >It seems almost certain that there must exist *some* (K, X, Y) such
that
> >
> >X XOR Y = DES_k(X) XOR DES_k(Y)
> >
> >though I think searching for one such tuple would be slightly slower
> >than breaking DES keys by brute force
>
> Irrelevant tangent: If for some reason you cared about finding such
> a (K,X,Y), you could find one with 2^29 encryptions using birthday
> paradox techniques. Fix an arbitrary k; re-write the equation as
> X XOR DES_k(X) = Y XOR DES_k(Y);
> generate 2^28 random values of X, and sort them by X XOR DES_k(X);
> generate 2^28 random values of Y, sorted by Y XOR DES_k(Y); finally,
> merge the two sorted lists and look for duplicates.
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Raphael Phan <[EMAIL PROTECTED]>
Subject: Re: DES question: Has this ever been proven before?
Date: Sat, 18 Nov 2000 06:48:15 GMT
Zulfikar Ramzan <[EMAIL PROTECTED]> wrote:
> So, if we pick any X, and set Y = DES(X) -- then the input
differential will be:
> X \xor Y = X \xor DES(X)
>
> The output differential will be:
>
> DES(X) \xor DES(Y)
> = DES(X) \xor DES(DES(X))
> = DES(X) \xor X.
Zulfikar, Brilliant! So I suppose for any weak key, as stated by Paul,
DES would become an involution and the situation where an input xor
causes the same output xor would exist. And for that to happen, since
there are 2^56 possible DES keys with 4 possible weak keys, the
probability would be 2^-54... very small, but still possible.
Thanks.
Raphael
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Raphael Phan <[EMAIL PROTECTED]>
Subject: Re: Rijndael: Impossible differential cryptanalysis on 5 rounds
Date: Sat, 18 Nov 2000 06:59:22 GMT
Zully,
Thank you for your reply. If you refer to the paper on impossible
differential cryptanalysis of 5-round rijndael, they are looking for a
pair of plaintexts satisfyinng the criteria. In Rijndael, a plaintext
is a 16-element byte array...
The pair has to have only one non-zero byte xor value while the other
15 xors should be zero, meaning they should differ in only one byte. I
cannot see why there are 2^40 pairs satisfying this criteria.
Thanks.
Raphael
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Raphael Phan <[EMAIL PROTECTED]>
Subject: Re: Rijndael: Impossible differential cryptanalysis on 5 rounds
Date: Sat, 18 Nov 2000 07:02:17 GMT
Zully,
By the way, here is the link to the paper...
http://csrc.nist.gov/encryption/aes/round2/conf3/papers/35-ebiham.pdf
Raphael
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: help on user authentication protocol
Date: 18 Nov 2000 00:02:05 -0800
[EMAIL PROTECTED] writes:
>
> Tom, thanks for your reply. I indeed already read your paper and also
> checked out SRP project website. Sorry for my naive question here
> becuase I am really new to this area. I want to ask you that if it is
> safe to put the prime number N and its generator g in the source code.
> I am thinking the "g" at least has to be hard-coded. Is that right?
Yes, N and g can be hard-coded. Just make sure that N is a safe prime
and that g is primitive (and that N is big enough).
> Your insight on implementation of your protocol will be greatly
> appreciated. BTW, I don't see the license statement of SRP on your
> website. You only say it's open-source friendly. But I would like to
The formal license statement is in the "docs/LICENSE" file in the
distribution. It's a BSD-style license, similar to the Apache and
OpenSSL licenses.
> see a formal license statement on your website. You also seem to
> imply that Standford is seeking patent on SRP. This concerns me. How
> do you ensure SRP is still a open-source protocol if your employer wants
> to get royalty on it?
Any issued patent will not affect the royalty-free status of the
technology, a la CAST-128, MD5, DES, or DSA.
> c6ap
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
--
Tom Wu * finger -l [EMAIL PROTECTED] for PGP key *
E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in
Phone: (650) 723-1565 exchange for security deserve neither."
http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Q: fast block ciphers
Date: Sat, 18 Nov 2000 10:39:03 GMT
In article <[EMAIL PROTECTED]>,
Lauri Pesonen <[EMAIL PROTECTED]> wrote:
>
> Hi,
>
> I'm trying to figure out, which block cipher would fit my needs the
> best. I'm in need of a very fast block cipher that could be used to
encrypt
> multiple (as many as possible) simultanious network streams. The
system
> would also use Matt Blaze's RKEP Protocol [1] (which requires a block
> cipher instead of a stream cipher). The main point is that multiple
streams
> should be encrypted with as small a CPU load as possible. Decryption
is not
> all that performance sensitive (of course it's not a minus if
decryption is
> fast as well). The cipher should be strong in the present day as well
as for,
> let's say, the next five years.
>
> I seem to remeber hearing from someone that blowfish is relatively
> fast. Any faster block ciphers out there?
>
> Thanks for all your help.
>
> [1] Blaze, M., "High-Bandwith Encryption with Low-Bandwith
Smartcards",
> December 3, 1995.
>
> --
> Lauri
>
Blowfish is fast, as is Rijndael. Though both can use 128-bit keys,
Blowfish has a 64-bit block and Rijndael has a 128-bit block. Analysis
of these ciphers shows that Rijndael requires more plain-text to break
than Blowfish but i'm not sure of the realtive speeds.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: [Question] Generation of random keys
Date: Sat, 18 Nov 2000 10:52:58 GMT
In article <[EMAIL PROTECTED]>,
Shri Desai <[EMAIL PROTECTED]> wrote:
> Hi,
>
> Can someone point me to source code (C or VB) to generate good random
> keys (1024 bit)? Good enough to be used in Diffe Helman algo.
>
> Would appreciate it,
>
> Thanks,
>
> Shri
>
There is plenty of entropy in a computer, but getting to it is tough.
If you want to generate random bits, the collect the LSB's from devices
that frequently change there status. e.g. Take the LSB from the X, Y
position of the cursor, Collect the LSB's from a string of key-presses.
This is a fudge however, its much better tap a real random source using
specialist equipment.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: MUST READ IN ORDER TO UNDERSTAND ASTROLOGICAL ORIGINS
Date: Mon, 13 Nov 2000 09:50:12 +0100
Pete Stapleton wrote:
<I dont care really>
Go away - Take your pseudoscience with you.
/Ichinin
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Cryptogram Newsletter is off the wall?
Date: Sat, 18 Nov 2000 14:28:18 GMT
About the signatures. Perhaps Mr Schneier forgot that private keys are
often password protected. Unless "Alice" has a poor or easy to guess
password it's not so easy to use her signature without her knowing.
And like real signatures I could forge it anyways without her knowing.
I simply don't get what his point was.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Hitachi - on what grounds ??
Date: Sat, 18 Nov 2000 14:51:34 GMT
On Sat, 18 Nov 2000 04:32:22 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote,
in part:
>Well, of course. What was I thinking?
Actually, I should have been more specific. I believe I did see this
invention on the page describing your various designs, but I didn't
look at the patent, and only by looking at that do I see the breadth
of the particular invention.
>The claims were and are at the end of the patent.
Thank you.
The term "one-way diffusion layer" meant, I suppose, a layer providing
diffusion in one direction, so I tend to think that the "laxy man's
cipher" notion I mentioned, once corrected to do diffusion properly,
would indeed infringe.
Of course, only now (thanks to your comment) do I see what would have
to be done to it: if enciphering diffuses, deciphering does not, so
one needs at least four layers, which makes the cipher open to the
same criticism you recently applied to the EDE variant of Triple-DES.
(If enciphering diffused, but deciphering didn't, there would be
vulnerability to known-plaintext attacks, of course.)
I think I'm going to have to dig around to see if there is any prior
art. Latin square combiners and dynamic substitution are far enough
out of the mainstream, but the idea of enciphering a text record by a
method that causes diffusion, first one way, and then the other, may
well have been used on mainframes for speedy, but not particularly
secure, encryption.
(There's even patent 5673319 of Mihir Bellare, which discusses doing
this on an entire file, for a different purpose, but that was later
than yours.)
While what Unix used for that is well known - a one-rotor 256-contact
pseudo-Enigma - there was an encryption program for MTS (the Michigan
Terminal System) designed shortly after DES came out that may have
used this principle, so that's what I'm going to dig up. Also, Multics
used some sort of file encryption, with the type of which I am not
familiar. (The example used by James Martin in his security book was a
digraphic cipher, so I don't have to worry about that one.)
I see it was filed in 1995; the claims do seem to be broad enough to
cover the sort of thing I'm thinking about. (There seems to be one odd
deficiency in the claims, in that they tend to refer to two, rather
than two or more, diffusion layers.)
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Mikael Lundqvist <[EMAIL PROTECTED]>
Crossposted-To: comp.compression
Subject: Re: Integer encoding on a stream
Date: Sat, 18 Nov 2000 15:35:46 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> MTF should result in most of the values being small. The lengths of
> these numbers should all be nearly the same, so entropy encoding on the
> lengths should work quite well. Additionally, the second part (all of
> the data bits) should hopefully be quite short.
>
To get at least closer to the highest possible compression we should add
as little information as possible.
It just hit me that geo in the Calgary corpus is a sequence of numbers (2
or 4 bytes units?). There were reordering of great help. 4.28 bpc without
and 3.92 bpc using recordsize 2 and my BWT.
To encode these integers, recordsize 4 should help.
Regards,
--
Mikael Lundqvist
mailto:[EMAIL PROTECTED]
http://hem.spray.se/mikael.lundqvist/
Who said:
"If a solution is simple, then it's probably correct!"?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Book recommendation, please
Date: 18 Nov 2000 15:52:21 GMT
Rex Stewart <[EMAIL PROTECTED]> wrote:
> I am surprised no one suggested "Handbook of Applied Cryptography"
> Should I take that to mean it would be overkill?
It's a reference, not an introductory text. While it's aimed at a
practicioner who isn't a mathematician (note the absence of proofs),
it still requires some "mathematical maturity."
That is, you need to be comfortable parsing sentences like
"Each party playing the role of A selects a random integer a,
1 < a \leq n_S - 2 and computes its ElGamal signature
public key u_A = \alpha^\a mod n_S."
(obtained by opening to p.513 and reading the first sentence which
came to my eye).
If you don't have such an ability, the best way to acquire it is by
trying to read such sentences and make sense of them...but this is
rough going. I hate to use words like "overkill," since there's some
benefit still, but I wouldn't suggest that _HAC_ be a 16-year-old's
only book on the subject.
For an introduction, _Applied Cryptography_ is better because of the
chapters which explain what these primitives are about and how to use
them. The intuition is extremely important and Schneier explains it well.
On the other hand, if you are going to implement anything, you'll want the
Handbook around. Not only does it fill in some of the details, but it
sometimes has better/faster ways of doing things than _Applied
Cryptography_ does.
Maybe the best thing to do would be to start with AC and then download
chapters of the Handbook as necessary. They're available online at
http://www.cacr.math.uwaterloo.ca/hac/
-David
------------------------------
Date: Sat, 18 Nov 2000 16:24:41 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Enigma development
A 57 year old man has been arrested and is being questioned by
Buckinghamshire police in Milton Keynes Police Station (a few miles from
Bletchley, and about the same distance from my house, and no, I'm not 57
years old!) with regard to the Enigma theft, according to a BBC Radio 4
news report.
The rotors have still not been recovered.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Book recommendation, please
Date: 18 Nov 2000 16:00:12 GMT
Greggy <[EMAIL PROTECTED]> wrote:
> You know, it would be pretty cool if there was an online high school
> course on the subject both in general and on specific topics. Free, of
> course.
Until that day, one place to start may be with Avi Rubin's list of
online cryptography courses.
http://avirubin.com/courses.html
What would an online high school course look like?
for that matter, what would you do if teaching cryptography to
high school students? what have people done?
-David
------------------------------
From: Bruce Schneier <[EMAIL PROTECTED]>
Subject: Re: Cryptogram Newsletter is off the wall?
Date: Sat, 18 Nov 2000 10:43:23 -0600
On Sat, 18 Nov 2000 14:28:18 GMT, Tom St Denis <[EMAIL PROTECTED]>
wrote:
>About the signatures. Perhaps Mr Schneier forgot that private keys are
>often password protected. Unless "Alice" has a poor or easy to guess
>password it's not so easy to use her signature without her knowing.
>And like real signatures I could forge it anyways without her knowing.
We've reached the point where passwords do not provide security
against off-line attacks.
There is an upper limit of what people can be reasonably expected to
remember and type in. And over the years, the efficacy of dictionary
attacks has increased. A few years ago, the two crossed.
Look at programs like L0phtCrack.
In any case, passwords are besides the point. If I have a Trojan on
your computer, I can easily wait until you type your password and
decrypt your private key...and then steal it.
Bruce
**********************************************************************
Bruce Schneier, Counterpane Internet Security, Inc. Tel: 408-556-2401
3031 Tisch Way, Suite 100PE, San Jose, CA 95128 Fax: 408-556-0889
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Hitachi - on what grounds ??
Date: Sat, 18 Nov 2000 17:13:17 GMT
On Sat, 18 Nov 2000 14:51:34 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (John Savard) wrote:
>[...]
>I see it was filed in 1995; the claims do seem to be broad enough to
>cover the sort of thing I'm thinking about. (There seems to be one odd
>deficiency in the claims, in that they tend to refer to two, rather
>than two or more, diffusion layers.)
That particular situation is not a deficiency: patent claims "cover"
or "read on" any system which even includes what is described. A
claim does not have to cover the complete implementation (else one
could just add a useless thing and a claim would not count).
The ideal claim has as few restrictions and limitations as possible,
consistent with the advance beyond any previous publication.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
Subject: Re: Cryptogram Newsletter is off the wall?
Date: Sat, 18 Nov 2000 17:16:46 +0000
Tom St Denis wrote:
>
> About the signatures. Perhaps Mr Schneier forgot that private keys are
> often password protected. Unless "Alice" has a poor or easy to guess
> password it's not so easy to use her signature without her knowing.
> And like real signatures I could forge it anyways without her knowing.
>
> I simply don't get what his point was.
"Mathematically, it works beautifully. Semantically, it fails
miserably."
His point was that 'digital signatures' had nothing to do with
mathematics of cryptography, but the engineering of systems.
The jist is that by using a typical untrusted non-secure PC you cannot
be reasonable certain that the underlying software of the application,
Operating System, and related hardware and software components **work as
intended.**
In other words: We cannot verify that the person 'signing' is signing
the document they thought they were signing. They have to trust the
software, and PC, and given the quality and correctness of typical
off-the-shelf hardware and software that confidence should not be there.
We know of worms, trojans, errors, etc. which comprimise systems all the
time. There is no reason to trust RSA / DSS running on these same
personal computers written by the same sort of programmers for the same
sort of commerical application companies that produce buggy software,
which is a well-known fact.
I'll leave it to you to re-read the essay to see the sort of attacks he
outline as easily possible, which can compromise the security of a
digital signature. Hint: the paragraph that starts with PGP.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Hitachi - on what grounds ??
Date: Sat, 18 Nov 2000 17:46:42 GMT
Since this all seems to justify a closer look, I re-examined your
patent more carefully, to see how it may resemble Rijndael.
Rijndael certainly does have a layer in which bytes are substituted.
And it has diffusion layers in between.
The diffusion is not one-way in the Mix Column step; all four bytes in
the column are thoroughly mixed with each other.
The Shift Row step does provide diffusion, but by moving pieces of the
columns around, not by adding something to one column from a preceding
one.
But the sort of thing I was thinking about as the "lazy man's cipher"
may well be related, although it lacks one critical element of your
design.
What I believe may have been done a few times is a cipher which
doesn't have any confusion layers, but which only has alternating
one-way diffusion layers which operate not in a way that resembles the
CBC block cipher mode, but in a way that resembles the OFB block
cipher mode:
| | |
(+) -->(+) -->(+)
| | | | |
| --- | --- |
| |S| | |S| |
| --- | --- |
| | | | |
|--- |--- |
Since this doesn't require creating an S-box that is invertible, it
can be done in a "quick-and-dirty" fashion.
The problem with this is that it only provides diffusion in one
direction in _another_ sense, as you've noted; as pictured, diffusion
does take place to the right when enciphering, but the corresponding
deciphering operation does not cause diffusion. (This is, of course,
why OFB is one of the standard block cipher modes; it has good
error-propagation characteristics.)
A more elaborate version of this sort of encipherment might,
therefore, work like this:
---> encipherment
Vigenere with the key
<--- encipherment
Rail-fence transposition
---> decipherment
Vigenere with the key
<--- decipherment
where the "decipherment" is constructed somewhat differently from the
encipherment, and the rail-fence transposition in the middle is aimed
at further avoiding problems with the decipherment, using the same
S-box, inverting the encipherment.
This sandwich structure, though, is weak against the "boomerang"
attack, but people using such simple methods would not be likely to
worry about that - and, in fact, unaugmented differential
cryptanalysis would work well against such constructs.
Thus, while I think that concepts resembling that patent may have been
in use in scrambling systems that weren't taken very seriously (and
hence may have left little trace in the literature), as your designs
involve in-line substitution, and other measures taken that make them
into something that _can_ be taken seriously, your priority in that
regard should be quite safe.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
** 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
******************************
