Cryptography-Digest Digest #791, Volume #11 Tue, 16 May 00 16:13:01 EDT
Contents:
Re: Recommend traffic analysis references. (Was: Mixmasters encrypt how?) (David A
Molnar)
Re: Destructive crypting (Tim Tyler)
Re: NIST release's final NSA report on AES HW performance (Roger Schlafly)
Re: bamburismus (Joaquim Southby)
NIST releases final AES comments (DJohn37050)
Re: Recommend traffic analysis references. (Was: Mixmasters encrypt how?) (David A
Molnar)
Re: Key generation (Eric Lee Green)
Re: Is OTP unbreakable? (Joaquim Southby)
New C++ radom number generator (Richard Wagner)
Re: Creating a good key-shedule (Tom St Denis)
Re: Definition of "Broken" Cipher (Tom St Denis)
Re: Is OTP unbreakable? (Johnny Bravo)
Re: Is OTP unbreakable? (Roger Carbol)
Is NovaStar DataSafe using Blowfish encryption any good? ("Lorraine")
Re: Key generation (Will Rose)
Re: Is OTP unbreakable? (William Rowden)
Re: Definition of "Broken" Cipher (Paul Koning)
----------------------------------------------------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Recommend traffic analysis references. (Was: Mixmasters encrypt how?)
Date: 16 May 2000 18:46:03 GMT
In sci.crypt William Rowden <[EMAIL PROTECTED]> wrote:
> Would someone recommend references that discuss traffic analysis? I'm
> asking for references because the Mixmaster protocol has intrigued me
> recently, and I'd like more background information for digital mixes.
I would like some more background on traffic analysis as well. I am
currently writing a related works section for an anonymous publishing
service, and it has a section on mixnets...
* Mixmaster and Remailer Attacks
Lance Cottrell's essay on the design rationale for the Mixmaster
remailers. Argues for having all messages the same length, for message
pools, and for random reordering of messages. Doesn't analyse any of
this mathematically -- that comes later and by other people if ever.
NOTE : there is a mailing list for discussing current mixmaster
implementation. it's at [EMAIL PROTECTED] -- to subscribe, e-mail
[EMAIL PROTECTED] . To find the current version of Mixmaster
(2.9b22), go to mixmaster.anonymizer.com .
* Babel
C. Gulcu and G. Tsudik
http://www.isi.edu/~gts/paps/guts96.ps.gz
Proposes an anonymous remailer system which is very similar to
Mixmaster. Outlines two active attacks which make traffic analysis much
easier for an adversary :
-- Flooding attack : The adversary sends many many messages
to the remailer and fills up its
message pool except for a few slots.
-- Trickle attack : Adversary stops all incoming messages
for the remailer, except one. Then it
watches to see what the remailer does
to that one message.
Defines a "miss factor" and "guess factor" to quantify the ability of
the adversary to perform traffic analysis. Carries out some preliminary
mathematical analysis on several techniques like batching and random
delay and tries to show how they make mix nodes resistant to attack.
* S-DATM -- "Secure Dynamic Adaptive Traffic Masking"
A paper on this appeared in the 1999 New Security Paradigms Workshop,
which I get because I'm an ACM SIGSAC member (best $9 ever spent).
There is a report from that conference in the IEEE Cipher at
http://chacs.nrl.navy.mil/ieee/cipher/old-conf-rep/conf-rep-nspw99.html
I didn't find that paper online, but this tech report
ftp://ftp.usc.edu/pub/csinfo/tech-reports/papers/96-641.ps.Z
seems to be related
I don't understand this paper yet, and I'm not going to try to summarise
it. Sorry.
* The Pfitzmanns and Friends' 80's papers on ISDN MIXes
The first proposed application of MIXes that I know of after David
Chaum's paper was to protecting a user's location on an ISDN network.
This led to many, many papers on the intersection of MIXes and public
telephone networks -- and more recently, mobile telephone networks.
Began with Birgit Pfitzmann, Andreas Pfitzmann, and other German
researchers, still going strong today.
Check the SIRENE list of publications on untraceable communications
at
http://www.semper.org/sirene/lit/sirene.lit.html#untrace
* David Michael Martin's thesis on "Local Anonymity in the Internet"
http://www.cs.du.edu/~dm/anon.html
This is a 1999 PhD thesis on providing anonymity in the Internet. It
has a comprehensive related works section which covers pretty much
everything you might want to read about in English. What's more, he
proposes and implements several new protocols for providing anonymity.
* Stop-and-Go MIXes
Dogan Kesdogan, Jan Egner, and Roland Büschkes
http://link.springer.de/link/service/series/0558/bibs/1525/15250083.htm
Picks up the mathematical analysis where Babel left off. Defines a
notion of "probabilistic anonymity" in terms of the adversary's ability
to perform traffic analysis to gain information about a message passing
through a mix node. Then shows how the mix can be modelled using
queueing theory and various things proved about it.
Dogan Kesdogan also has a short prospectus of his work at
http://www-i4.informatik.rwth-aachen.de/staff/homes/dogan/privacy_flyer.pdf
which points to other work he's done on mix-nets.
* "Web Mixes" and Project: Anonymity and Unobservability in the Internet
Hannes Federrath and company
The project page :
http://www.inf.tu-dresden.de/~hf2/anon/
The project prospectus, including their declaration of intent to
develop a model for traffic analysis :
http://www.icsi.berkeley.edu/~hannes/rp.html
An upcoming workshop on anonymity :
http://www.icsi.berkeley.edu/~hannes/ws.html
* TAZ and Rewebber
A system which uses web servers as mix nodes to allow the publication of
"pseudonymous" URLs. Mentions traffic analysis, and points out that
high-latency countermeasures like random reordering and delay of
messages just don't work in a real-time setting.
http://www.cs.berkeley.edu/~daw/classes/cs268/taz-www/rewebber.html
See also www.rewebber.de, which AFAIK isn't related to Goldberg or
Wagner, but is instead the commercial incarnation of the old Janus
system.
* Onion Routing
http://www.onion-router.net/
A mix-net for TCP/IP. I don't remember at this point how much they
discuss traffic analysis if at all.
* Zero Knowledge Systems
http://www.freedom.net/
Mix-net for mail and TCP/IP. Plans to include "traffic shaping" to
thwart traffic analysis on TCP/IP at some point, but not in the
current version.
That's all I can remember at this point. There are also proxy services
like the Anonymizer and those managed by Proxymate, and also the AT&T
Crowds system, but they aren't mix-nets per se. Hope I didn't leave too
much out...
Thanks much,
-David
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Destructive crypting
Reply-To: [EMAIL PROTECTED]
Date: Tue, 16 May 2000 18:37:25 GMT
Mark Wooding <[EMAIL PROTECTED]> wrote:
: Tim Tyler <[EMAIL PROTECTED]> wrote:
:> Sometimes folks seem to use use Hash(Key,Message) as a way of building
:> MAC(Message). Doing this may be slower than using a dedicated MAC.
: There are better reasons not to use this construction.
: Most hash functions in common use divide the preimage into fixed-size
: blocks and process each in turn. It's therefore possible to compute the
: hash of a message M' = M || m given only the hash of the original
: message H(M) and the suffix m. Using the above construction then lets
: you forge a MAC for any suffixed message you already have a MAC for.
: Which is a shame.
You could prepend the length of the message (padded up to 64 bits) between
the key and the start of the message. I believe that would effectively
kill off this attack.
Appending it would probably work as well - which would help as you're
more likely to have the message length to hand at the end of its
transmission rather than at the start.
I'm sure it's better to use a purpose-designed MAC, though.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Goodbye cool world.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: NIST release's final NSA report on AES HW performance
Date: Tue, 16 May 2000 12:09:36 -0700
DJohn37050 wrote:
> NIST released on 5/15/2000 the final NSA report on AES finalist performance.
Get it and related materials at the AES site:
http://csrc.nist.gov/encryption/aes/
No clear winner, but it looks like Mars is inferior in hardware.
------------------------------
From: Joaquim Southby <[EMAIL PROTECTED]>
Subject: Re: bamburismus
Date: 16 May 2000 19:10:59 GMT
In article <8fruu1$d27$[EMAIL PROTECTED]> Ferrante Formato,
[EMAIL PROTECTED] writes:
>Any information about Turing's Bamburismus?
>It was a probabilistic meythod settled to crack Enigma code in WWII
>
Try these:
http://www.cranfield.ac.uk/ccc/bpark/lectures/ts-jan14-1999.txt
http://web-cr05.pbs.org/wgbh/nova/decoding/mind3.html
David Kahn in "Seizing the Enigma" spends about three pages describing
banburismus (note the spelling if you'd like to do some web searches).
Unlike the Nova site listed above, he doesn't mention a machine doing the
work.
I haven't read it yet, but I believe "Station X: Decoding the Nazi
Secrets" by Michael Smith also has some info.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: NIST releases final AES comments
Date: 16 May 2000 19:25:07 GMT
NIST releases final AES comments. See Round 2 comments. Some are in separate
files and some are in a big text file if sent as a note.
Don Johnson
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Recommend traffic analysis references. (Was: Mixmasters encrypt how?)
Date: 16 May 2000 19:04:48 GMT
David A Molnar <[EMAIL PROTECTED]> wrote:
I forgot one :
* PipeNet by Wei Dai
http://www.eskimo.com/~weidai/pipenet.txt
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: Key generation
Date: Tue, 16 May 2000 19:32:20 GMT
PBanaugh wrote:
> Anybody know of a good way to generate a pseudorandom key from a user's
> passphrase?
>
> Here's my idea. Let me know how good or bad this is...
>
> 1) Get a passphrase P.
>
> 2) Hash P with SHA-1, giving result H.
Once you have done this, you have distilled all of the entropy that's in the
passphrase. All other operations you do aren't going to give you any more
entropy.
If you want more randomness, hash in a random salt value S. You'll need to
store this S into the file so that you can decrypt the file at the other end
though. So:
1b) get random hash value S.
1c) Save random hash value S on output.
2) Hash P+S with SHA-1, giving result H
then use H.
All the other transform stuff you mentioned will be very slow, but give no
more strength that this algorithm. Your passphrase has a limited entropy,
meaning that the outputs generated by your passphrase will be a subset of the
possible outputs no matter what you do to your passphrase. By adding a
different random number into the passphrase for each encryption, you are in
effect encrypting each file with a different key, thus defeating attacks that
require a lot of ciphertext all encrypted with the same key. This at least
helps with the problem of the limited entropy, though doesn't solve it.
> The idea is to transform the passphrase into a key that is as random as
> possible. Real real numbers can't be used because they cannot be
> re-generated (at least not if they're truly random) in order to recreate
> the key for decryption.
Just store the random number into the file, and fetch it back at the other
end. Doesn't lose you anything, you still have the same number of bits of
entropy.
The other alternative is to use the passphrase to unencrypt a key file or "key
chain" a'la' PGP, and the actual file(s) encrypted are done with a totally
random key decrypted out of the key chain. This is what PGP does, and relies
on the fact that your key chain resides on your hard disk and is not ever
transmitted where it could be intercepted (hopefully!).
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer Visit our Web page:
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
From: Joaquim Southby <[EMAIL PROTECTED]>
Subject: Re: Is OTP unbreakable?
Date: 16 May 2000 19:34:17 GMT
In article <8fr420$j1o$[EMAIL PROTECTED]> Simon Johnson,
[EMAIL PROTECTED] writes:
>So the OTP is unbreakable, but isn't very useful. For a start the key
>can only be used once:
>
>(Cipher-text one) = (text 1) XOR (Key)
>(Cipher-Text two) = (text 2) XOR (key)
>
>:. solving simulatneously.
>
>(Cipher-text One) XOR (text 1) = (text 2) xor (Cipher-Text two)
>
>It is clear from this that you can solve the two cipher-texts without a
>key, making it easily breakable.
>
Can you explain this in a little more depth, please? Your first two
equations contain 3 unknowns (text 1, text 2, key); the third equation is
derived from the first two and contains no new information (it actually
reads key = key). You can't solve 3 unknowns with only two independent
equations -- assumptions must be made somewhere.
Supposedly, the cipher solver possesses only the two cipher texts. If
those are XOR'ed, what's left is the two plaintext messages XOR'ed
together. At this point, cribs (standard headers, common names, etc.)
could be applied if they exist. If they don't exist (say if the
plaintext was a language unknown to you or was random data), would it be
possible to decipher the messages?
I'm not disputing your assertion that reusing the OTP keystream leads to
vulnerabilities; I just don't understand how one would go about breaking
the ciphered texts without additional techniques.
------------------------------
From: Richard Wagner <[EMAIL PROTECTED]>
Subject: New C++ radom number generator
Date: Tue, 16 May 2000 19:28:58 GMT
I have recently written a C++ implementation of the Mersenne Twister
random number generator. My personal use of it is for Monte Carlo
simulations, but I want to make it as useful as possible for others
too. So, I am interested in feedback on its applicability to
cryptography. The features include:
* Enormous period, 2^19937-1
* Fast (2.5x the speed of rand() )
* Automatic seeding from /dev/urandom or time() and clock()
* Manual seeding with up to 19937 bits
* Ability to save and load state
* Open source under GNU Lesser General Public License
The source code and more info are at
http://www-personal.engin.umich.edu/~wagnerr/MersenneTwister.html
A couple of specific questions:
I use /dev/urandom as the default seed source since /dev/random might
leave the program waiting for entropy; should I add a "secure" option
which demands /dev/random instead?
I do not hash the output, so the state of the generator can be learned
after seeing 624 numbers. I reasoned that the programmer using the
class can choose a better secure hash algorithm than I can include
myself. And, as far as I know, hashing is unneccesary for simulations.
Would including a default hash be useful? Are there any available under
the LGPL?
--
Richard J. Wagner, Graduate Student
University of Michigan
Department of Chemical Engineering
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Creating a good key-shedule
Date: Tue, 16 May 2000 19:29:40 GMT
In article <8frrvo$e79$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> I've been trying to magic up a 32 round Fiestel-type block-cipher for
> some time now, (although its prolly very poor.)
>
> As a bit of background i'll detail the parts of the algorithm.
>
> The Cipher has a 16-bit block length and a varible length key, 0 to 32
> bytes.
A 16 bit block doesn't make for a very secure block cipher.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Definition of "Broken" Cipher
Date: Tue, 16 May 2000 19:26:14 GMT
In article <[EMAIL PROTECTED]>,
Paul Koning <[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
> >
> > In article <[EMAIL PROTECTED]>,
> > Paul Koning <[EMAIL PROTECTED]> wrote:
> > > Tom St Denis wrote:
> > > >
> > > > It's quite simple. You don't say your car is broken because of
a
> > dent
> > > > in the fender right?
> > > >
> > > > Well if I can attack a cipher X, in 2^100 steps is it really
broken?
> > > > Let's see, does it secure information? Yes. How is that
broken?
> > > >
> > > > I think the definition of "broken" for a cipher is when finding
the
> > key
> > > > and/or plaintext from ciphertext only is easier then brute
forcing
> > the
> > > > key.
> > >
> > > Absolutely not. That's a dangerously weak standard.
> > >
> > > Chosen plaintext attacks are clearly feasible in practice in
> > > many cases. Known plaintext attacks have been used for centuries.
> > >
> > > > Let's be realistic, getting 2^50 pairs of plaintext/ciphertext
is
> > not
> > > > possible for two reasons. a) Bandwidth, b) smart people re-key
> > their
> > > > ciphers.
> > >
> > > That may be true. Or maybe not. Remember how quickly the
> > > total throughput of the Internet is increasing.
> >
> > However most sane protocals will re-key to avoid using the same key
for
> > any long period of time. Say every 2^20 blocks....
>
> 2^20 blocks is NOT a long time! That's only 64 (or 128 for AES)
> megabits. That's less than a second of traffic for the sort of
> high speed links you can get as a high end Internet *user*, never
> mind the far faster links used in the Internet core. (The latter
> are less relevant since encryption is normally an end to end
> activity. But if you have an OC-3 link into the Internet, you're
> not particularly likely to rekey as often as you suggest, not
> by a long shot.
For the rest of the world... 2^20 blocks for a 64-bit cipher is 8
megabytes which is quite a bit for private use.
On a huge ISP chances are the terabit data is not being sent to the
same client anyways.... it makes no sense...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Johnny Bravo <[EMAIL PROTECTED]>
Subject: Re: Is OTP unbreakable?
Date: Tue, 16 May 2000 15:32:51 -0400
On Tue, 16 May 2000 09:23:22 GMT, Simon Johnson
<[EMAIL PROTECTED]> wrote:
>resultant cipher-text. Therefore the cipher-text is just as random as
>the PAD.
Which is the whole point, unbreakable encryption.
>The only information that can be recovered from the cipher-text is the
>length. The fact the output is random means it contains no information,
>therefore it has no redudancies that can be analyised.
Actually, you only get the upper bound on the length of the
plaintext. The plaintext could be far shorter than the ciphertext.
>So the OTP is unbreakable, but isn't very useful. For a start the key
>can only be used once:
Not much of a limitation. If you use the key more than once you are
not using a OTP. The O in OTP stands for "One".
>Moreover, the key has to be the same length as the text you want to
>encrypt (repeating a key over the plain-text falls to an attack related
>to the one obove). Encrypting with a OTP is pointless simply because
>now you now have to figure out a way to secure the OTP key!!!!!!!
It is far from pointless, there are many situations where the key
can be secured but the message can not be. Like a transmission over
shortwave radio, or email on the internet, or posting to a newsgroup,
or publishing in a newspaper, or posting on a bulletin board, ect.
--
Best Wishes,
Johnny Bravo
"The most merciful thing in the world, I think, is the inability
of the human mind to correlate all it's contents." - HPL
------------------------------
From: [EMAIL PROTECTED] (Roger Carbol)
Subject: Re: Is OTP unbreakable?
Date: Tue, 16 May 2000 19:47:15 GMT
>>> The only information that can be recovered from the cipher-text is
>>> the length.
I'm not sure this is strictly true. Does "the length" refer to the
length of the plaintext? Padding could make that unrecoverable.
Indeed, to defeat certain types of message traffic analysis, it
could be very important to make all the outgoing ciphertexts
the same length.
Or does it refer to the length of the ciphertext? I'll be the first
to agree that one can recover the length of the ciphertext from
the ciphertext itself. That and a quarter will get you a cup of
coffee.
.. Roger Carbol .. [EMAIL PROTECTED]
------------------------------
From: "Lorraine" <[EMAIL PROTECTED]>
Subject: Is NovaStar DataSafe using Blowfish encryption any good?
Date: Tue, 16 May 2000 14:50:59 -0500
Is NovaStar DataSafe using Blowfish encryption any good?
I need a program that is legal overseas,fairly easy to use for non-literate
computer users and is not easy to break.
------------------------------
From: Will Rose <[EMAIL PROTECTED]>
Subject: Re: Key generation
Date: 16 May 2000 19:57:10 GMT
Eric Lee Green <[EMAIL PROTECTED]> wrote:
: PBanaugh wrote:
:> Anybody know of a good way to generate a pseudorandom key from a user's
:> passphrase?
:>
:> Here's my idea. Let me know how good or bad this is...
:>
:> 1) Get a passphrase P.
:>
:> 2) Hash P with SHA-1, giving result H.
: Once you have done this, you have distilled all of the entropy that's in the
: passphrase. All other operations you do aren't going to give you any more
: entropy.
Is there an advantage to using a hash function over eg. a CRC of the
passphrase? Both conversions have a 1:1 correspondence between phrase
and key; the main problem seems to be that a CRC typically has only
32 bits of output. OTOH, it's cheap to generate.
Will
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (William Rowden)
Subject: Re: Is OTP unbreakable?
Date: 16 May 2000 20:03:50 GMT
In article <8forim$1h4$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> Is it possible to prove theoretically that OTP using a truely random
> key is unbreakable?
Having recently participated in a comparison of an OTP to a block
cipher (the thread "A naive question" started by Mok-Kong Shen on
4/28/2000), I'm beginning to see why the sci.crypt FAQ has this entry:
4.4. Why is the one-time pad secure?
> If there is a mathematical proof then I would be interested to know
> it...
As Bryan Olson pointed out, the mathematical explanation goes back at
least to Shannon's 1949 paper, "Communication Theory of Secrecy
Systems." I'll quote from http://www3.edgenet.net/dcowley/docs.html:
"It is shown that perfect secrecy is possible but requires, if the
number of messages is finite, the same number of possible keys." Of
course, "it is shown" refers to arguments later in his paper.
--
-William
PGP key: http://www.eskimo.com/~rowdenw/pgp/rowdenw.asc until 2000-08-01
Fingerprint: FB4B E2CD 25AF 95E5 ADBB DA28 379D 47DB 599E 0B1A
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Definition of "Broken" Cipher
Date: Tue, 16 May 2000 15:38:51 -0400
wtshaw wrote:
>
> In article <[EMAIL PROTECTED]>, Paul Koning
> <[EMAIL PROTECTED]> wrote:
> >
> > I think the reasoning goes like this: attacks only get better over
> > time. Therefore, *any* weakness is an opportunity for ever more
> > efficient attacks. Therefore, the prudent standard is "there exists
> > no known attack better than brute force search of the keyspace".
> >
> This sounds good, but the idea that keyspace is a simple monolith for each
> algorithm is bogus, since it may often be more or less user defined;
Good point. So you have to qualify that by the assumptions
about the key assignment mechanism. If a good one (say, D-H)
is used, then it's reasonable to treat the keyspace as a
monolith. Then you still (in theory) might have a cipher where
some keys are easier to find than others. (I don't know of
any modern ones with that property, though.)
> As for weakness, it is an arm wrestling contest between the cryptographer
> and any potential attacker. It matters more that the attackers do not find
> weaknesses that that the cyrptographer magically does not include any.
Not including weaknesses is of course something you can't prove -- the
usual problem of proving a negative.
> Much of cryptography is qualitative, in that deception is more powerful
> than good mathematics, although figuing that you adversary is dumb may be
> an act of strupidity on the part of the designer or user.
Well said. So a known weakness is always a concern. Once you know
there is a weakness, you must assume the opponent will find it too.
The opponent may also be smarter or luckier than you are and find
a weakness you didn't know about -- nothing you can do about that
(other than endeavor to be as skilled and as smart as possible).
> So, weakness, like strength for algorithms, is as elusive. I continually
> turn the search for weaknesses on its head and look for what makes
> strength., as it seems to me that this is as important a search as the
> other. How can you justify one without the other?
I think you're talking about the approach for finding strong ciphers,
as opposed to the way to look at breaks found in ciphers. In the
latter,
the weakness (its size, relevance, etc.) is the issue.
paul
------------------------------
** 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
******************************
