Cryptography-Digest Digest #577, Volume #10 Tue, 16 Nov 99 19:13:03 EST
Contents:
Re: more about the random number generator (William Rowden)
Re: AES Candidate Specs? (John Savard)
Re: AES cyphers leak information like sieves ([EMAIL PROTECTED])
Re: Modified DH - ok? (Glenn Larsson)
Re: Codebook examples on Web? ([EMAIL PROTECTED])
Re: AES cyphers leak information like sieves (DJohn37050)
Re: Proposal: Inexpensive Method of "True Random Data" Generation (James Felling)
Re: AES cyphers leak information like sieves (Tim Tyler)
Re: AES cyphers leak information like sieves (Tom St Denis)
Re:SCOTT16U SOLUTION ON THE WEB (Tom St Denis)
Re: more about the random number generator (Tom St Denis)
Re: AES cyphers leak information like sieves (Tim Tyler)
Re: Proposal: Inexpensive Method of "True Random Data" Generation
([EMAIL PROTECTED])
Re: Codebook examples on Web? (John Savard)
weak ciphers and their usage (Tom St Denis)
USENIX Annual Conference 2000 - Final Call For Papers (Moun Chau)
Re: Interested in bulk encrypt1on devices (John Savard)
Re: more about the random number generator ("Trevor Jackson, III")
----------------------------------------------------------------------------
From: William Rowden <[EMAIL PROTECTED]>
Subject: Re: more about the random number generator
Date: Tue, 16 Nov 1999 19:28:21 GMT
In article <80rg9d$p9s$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> In article <80qrm0$bb1$[EMAIL PROTECTED]>,
> William Rowden <[EMAIL PROTECTED]> wrote:
> > The *cryptographic* security of a PRNG is generally described in
> > complexity-theoretic terms. My first question is therefore "What's
> > the algorithm?" Security relies on the presumed intractability of
> > an underlying number-theoretic problem.
[snip]
> Truly random generators should not have any theoretic explanation
> though. I mean I can explain why this rng works, but not predict the
> output without knowing all the nicks and nannies of the win32 task
> scheduler.
I'm not familiar with your generator. For PRNGs, the theoretical
explanation is precisely what suggests that it is computationally
infeasible to predict the output. I infer from your comments and Scott
Nelson's comments that your RNG gathers entropy from system processes
instead.
> > I'd also try a poker test with m = 8, using the 8-bit byte option of
> > the program.
>
> I would have to make a huge file for diehard to use though, and this
> generator only outputs about 4 to 6 cps.... [32 to 48 bits per
> second].
[snip]
> I will try a run test on a 1MB file ...
What's 'diehard'? FWIW, the FIPS 140-1 standard requires a 20,000-bit
sample stream for the runs test and a 4-bit poker test.
--
-William
SPAM filtered; damages claimed for UCE according to RCW19.86
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
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: AES Candidate Specs?
Date: Tue, 16 Nov 1999 19:37:56 GMT
Paul Crowley <[EMAIL PROTECTED]> wrote, in part:
>[EMAIL PROTECTED] (John Savard) writes:
>> My web site contains descriptions of some of the AES candidates, that
>> I put in my own words. I tried to make them easier to understand, and
>> included diagrams in some cases. (I found MARS not to be too hard to
>> understand, but some of the others were more difficult.)
>Interesting. I think that RC6 is by far the simplest to describe,
>though not necessarily to analyse. If you understand GF(2^8) then
>Rijndael is definitely the next simplest; otherwise both Rijndael and
>Twofish will be incomprehensible. I guess I think of "simplest to
>describe" and "easiest to understand" as similar measures. MARS
>strikes me as one of the more difficult ones by any measure.
>Twofish is easily the most complex; it also has one of the best
>security margins by current analysis.
You'll note that my descriptions of Rijndael and Twofish include very
explicit descriptions of GF(2^8), as I don't assume familiarity with
it.
MARS is a lot like DES, and so there is a background I _can_ assume to
be present that I can build on. Also, because of that, MARS lent
itself to diagrams, which are a great advantage in explaining
anything.
John Savard (don't snooze, don't snore)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: AES cyphers leak information like sieves
Date: 16 Nov 1999 19:37:25 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
> DJohn37050 <[EMAIL PROTECTED]> wrote:
> : The break is expected to occur at the square root of the block size, due to
> : birthday paradox. For a 128-bit block, this is a LOT.
> sqrt(128) ~= 11 bits - less than 1.5 bytes.
Ummmm.... no. The relevant thing here is sqrt(2^128) = 2^64.
> If your data has regularities on the same scale as the size of your
> blocks, you should be /very/ cautious.
Are you just ignoring all the other posts that point out that ECB is a
silly and non-recommended way of encrypting things using these (or any
other) block cipher?
--
Steve Tate --- srt[At]cs.unt.edu | Gratuitously stolen quote:
Dept. of Computer Sciences | "The box said 'Requires Windows 95, NT,
University of North Texas | or better,' so I installed Linux."
Denton, TX 76201 |
------------------------------
From: Glenn Larsson <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Modified DH - ok?
Date: Tue, 16 Nov 1999 20:42:09 +0100
Hideo Shimizu wrote:
>We can compute secret value P from PtoQ*N^(-1) mod M and Q similar.
Correct - but only when P*N <= M:
Secret value P = 127
Secret value Q = 87
Public N = 255
Public M = 4738
QToP = 3233
PtoQ = 3957
SecretKey(s) = 796365
3957*255^(-1) mod 4738 = 16..
Rule 1: (Secretvalue * N) must be larger than M
Thanks 10^6,
Glenn
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Codebook examples on Web?
Date: 16 Nov 1999 19:51:28 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> I hope you can get permission from HMSO to put a few
> more pages up,
I purchased the book from a secondhand bookshop in Hay-on-Wye (Wales) a
few years ago. It's destined for the crypto archive at Bletchley Park.
> So the "BAMS code" was British Cypher No. 3? ...and these codes were
> compiled in the 1920s, far in advance of the war.
That's the supposition I'm making - I'd like to hear more about its
history - anyone?
Keith
http://www.cix.co.uk/~klockstone
------------------------
'Unwise a grave for Arthur'
-- The Black Book of Carmarthen
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: AES cyphers leak information like sieves
Date: 16 Nov 1999 19:51:53 GMT
This is known as the self-syncronizing property of CBC mode. You only lose 2
blocks due to a bit flip. Check it out if you do not believe it.
Don Johnson
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.misc,sci.physics
Subject: Re: Proposal: Inexpensive Method of "True Random Data" Generation
Date: Tue, 16 Nov 1999 14:00:30 -0600
Coen Visser wrote:
> James Felling wrote:
>
> > [...] Thus while this is a useful definition of random, it is a less than useful
>tool,
> > as by choosing apropriate L, a string X may be assigned any level of complexity
> > of representation from this string is string #0 of aour pool o' strings to this
> > string is representable in L, with k bits, to this string is not finitely
> > representable in language L.
>
> I agree with a small remark. You could fix a small UTM
> (which defines your representation language). This would
> take somewhere from 400 - 3000 bits depending on your
> computation model. Any other reasonable representation
> language can be simulated by the fixed UTM in a finite number
> of bits. It *could* argued that this can be done in a reasonable
> number of bits (say less than a few million). I wouldn't stake
> *anything* on it but it is not unthinkable.
>
> > I think Kolmogorov complexity is a useful thing, but as it is so very sensitive
> > to the representational language, it is a weak tool for the quantification of
> > randomness. In fact I have some doubt as whether there is a way it can be used
> > to label a single string that has any meaning beyond L.
>
> Kolmogorov complexity is mostly used not to determine
> the degree of randomness. The mere existence of random strings
> is used as a tool to prove all kinds of things in a very
> intuitive way.
>
My argument with you is that since K-Complexity is only valid in refrence to a chosen
language, the only way we can class things as random is relative to that chosen
language.
Now given strings X and Y,
It is comparitively trivial to chose languages such that complexity(X) in L and
complexity(Y) in L have any relationship that we wishthis is true even if X and Y are
sets
of strings -- we can arbitrarily dictate the realtion between any two finite
collections of
strings by apropriately choosing our language.
>
> Regards,
>
> Coen Visser
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: AES cyphers leak information like sieves
Reply-To: [EMAIL PROTECTED]
Date: Tue, 16 Nov 1999 19:59:57 GMT
I <[EMAIL PROTECTED]> wrote:
: DJohn37050 <[EMAIL PROTECTED]> wrote:
: : The break is expected to occur at the square root of the block size, due
: : to birthday paradox. For a 128-bit block, this is a LOT.
: sqrt(128) ~= 11 bits - less than 1.5 bytes.
This wasn't what you meant, of course ;-| sqrt(2^128) = 2^64 *blocks*.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Replace repetitive redundancies by calls to a common function.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: AES cyphers leak information like sieves
Date: Tue, 16 Nov 1999 20:36:56 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> The problem is simple: the AES cyphers are fixed 128-bit block
cyphers.
> The encode identical blocks in the same way. For certain types of
> message, this is a complete security disaster.
Cite specific systems that use ciphers in this manner. [hint hint CBC
or PCBC or CFB mode systems are more popular].
>
> To explain the problem I will present a simple parable:
No need to explain, apparently you two can't figure out that people
don't use ECB in real systems and that simply modifiying a byte of
ciphertext doesn't reveal the plaintext....
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re:SCOTT16U SOLUTION ON THE WEB
Date: Tue, 16 Nov 1999 20:44:19 GMT
In article <80rpvu$2dac$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
>
> Tom if your too stupid to understand that if a small fragment of a
file
> has enough info to allow an expert to have the information to test for
> a whole break is not less secure than another method where an attacker
> must have the whole file to even have enough info to attack the system
> then why do you waste our time in this group. You don't even have
enough
> understading to comprehend simple things.
First off from a naive brute force point of view WPCBC is conceptually
just as easy as CBC.
Second your primitive in wpcbc is still a block cipher. so if CBC is
easy to break, wpcbc can only make the problem LINEARLY harder [see
multiple encryptions for further details why].
I agree that your wpcbc proposal is a good idea for short messages. It
makes the entire message dependant. However you can't tell me that
it's good on multi-meg files and the sort [or live audio]. I don't
think that our current ciphers are in a state that any tractable
cryptanalysis can determine the plaintext simply by looking at a few
hundread blocks anyways.
What I am trying to say is that most attacks [form of cryptanalysis]
are on the CRYPTOSYSTEM and not the cipher. For example peekboo/pgp
can easily be kicked in the groin if the rng used to make keys is
defective.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: more about the random number generator
Date: Tue, 16 Nov 1999 20:48:13 GMT
In article <80sb7t$eme$[EMAIL PROTECTED]>,
William Rowden <[EMAIL PROTECTED]> wrote:
> I'm not familiar with your generator. For PRNGs, the theoretical
> explanation is precisely what suggests that it is computationally
> infeasible to predict the output. I infer from your comments and
Scott
> Nelson's comments that your RNG gathers entropy from system processes
> instead.
It simply a bit inverter...
do while _some_time_preferably_short_like_1_msec hasn't passed
a = not a
I added a twist though, I xored the lsb of a 1.19mhz timer [the PIT]
and I use the output in a shrinking style generator to throw out bits
at random.
IT relies on the fact that you are not sure how many cycles each task
will get per turn.
> What's 'diehard'? FWIW, the FIPS 140-1 standard requires a 20,000-bit
> sample stream for the runs test and a 4-bit poker test.
I will have to read it tonight :)
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: AES cyphers leak information like sieves
Reply-To: [EMAIL PROTECTED]
Date: Tue, 16 Nov 1999 20:47:26 GMT
DJohn37050 <[EMAIL PROTECTED]> wrote:
: This is known as the self-syncronizing property of CBC mode. You only lose 2
: blocks due to a bit flip. Check it out if you do not believe it.
OK, then - I'll look it up.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
You have junk mail.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.math,sci.misc,sci.physics
Subject: Re: Proposal: Inexpensive Method of "True Random Data" Generation
Date: Tue, 16 Nov 1999 20:57:22 GMT
Coen Visser wrote:
> [EMAIL PROTECTED] wrote:
[...]
> > Kolmogorov
> > complexity can define whether an infinite string
> > is compressible, but not whether a finite string
> > is compressible.
>
> It is good to separate the two cases, but I don't
> agree with your above statement. I would think that
> Kolmogorov complexity is properly defined on finite
> strings: the upperbound of C(Sn) with Sn the "0"-string
> of length n is log(n).
Since there is some constant C, such that for
all n, C(Sn) <= log(n) + C.
That's a description of the complexity of an
infinite set of (finite) strings. It makes
sense since the variable n takes arbitrarily
large values, and thus log(n) will dominate
any constant.
But the issue is whether an individual finite
string is compressible. In this case n has one
value so C(Sn) and log(n) are constants. The
inequality asserts the vacuous fact that two
constants differ by at most a constant.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Codebook examples on Web?
Date: Tue, 16 Nov 1999 21:42:45 GMT
[EMAIL PROTECTED] wrote, in part:
>In article <[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] (John Savard) wrote:
>> I hope you can get permission from HMSO to put a few
>> more pages up,
>I purchased the book from a secondhand bookshop in Hay-on-Wye (Wales) a
>few years ago. It's destined for the crypto archive at Bletchley Park.
You were extremely fortunate. Dare I ask if you needed to take out a
second mortgage?
John Savard (don't snooze, don't snore)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: weak ciphers and their usage
Date: Tue, 16 Nov 1999 21:35:27 GMT
Ok I actually see what David Scott is saying. I can be thought. If I
send a different message with say only a part near the ending changing
it won't change the entire file [ciphertext] and this can be used in an
attack. Not easily but it can be used and thus a weakness. This is
not inherant in the block cipher, but how it is used.
So ideally w-pcbc mode solves the problem of having to use key salts,
as long as your message changes each time you send it. Interesting
solution to when a RNG is not available. Good work David!
However the problem can be solved if you use key salts [problem of
having matching ciphertext] which is normally the accepted solution.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Crossposted-To:
comp.windows.x,hannet.ml.linux.rutgers.linux-admin,ieee.admin,misc.security,muc.lists.www-security,comp.mail.sendmail,comp.os.linux,comp.os.linux.hardware,comp.os.linux.networking,comp.os.linux.x,comp.unix.bsd.freebsd.misc,comp.unix.programmer
From: [EMAIL PROTECTED] (Moun Chau)
Subject: USENIX Annual Conference 2000 - Final Call For Papers
Date: Tue, 16 Nov 1999 21:44:09 GMT
2000 USENIX Annual Technical Conference
June 18-23, 2000
San Diego Marriott Hotel & Marina
San Diego, California, USA
http://www.usenix.org/events/usenix2000
Sponsored by USENIX, the Advanced Computing Systems Association.
Celebrating 25 years of technical leadership and growth, the 2000 USENIX
Annual Technical Conference invites all developers, researchers, and
users with interests ranging from embedded systems to Tcl/Tk, from
object-oriented programming to network administration, and from Internet
technologies and electronic commerce to using, managing, and researching
Windows NT. The USENIX 2000 Annual Technical Conference brings together
this broad community under a single roof to share the results of their
latest and best work, find points of common interest and perspective,
and develop new ideas that cross and break boundaries.
We are currently seeking submissions for Refereed Papers,
Works-In-Progress Reports, Tutorial and Invited Talk proposals, and
suggestions for our Birds-of-a-Feather sessions. We also encourage you
to submit papers for our FREENIX track, a special track dedicated to
exploring projects and solutions in progress. Topics of interest include
but are not limited to: Operating system and applications structure,
internet/intranet applications, development and security, e-commerce,
Tcl/tk, Perl, embedded systems, Windows NT, network admin, object
oriented programming, and the latest in technology and system management
techniques.
Please see the detailed submission guidelines and conference
information: http://www.usenix.org/events/usenix2000/cfp
=====================================================
IMPORTANT DATES FOR SUBMISSIONS
*Paper Submissions deadline: November 29, 1999
*Notification to authors: January 26, 2000
*Full papers due for editorial review: March 28, 2000
*Camera Ready papers due: April 25, 2000
=====================================================
USENIX is the Advanced Computing Systems Association. Its members are
the computer technologists responsible for many of the innovations in
computing we enjoy today. To find out more, visit our web site:
http://www.usenix.org.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Interested in bulk encrypt1on devices
Date: Tue, 16 Nov 1999 21:51:28 GMT
zenlight <[EMAIL PROTECTED]> wrote, in part:
>Does anyone have information on the bulk encryp-
>t1on devices listed in
>http://sva.theriver.com/millist/m14.html#a2761
Not that they're allowed to share...
I do remember that one of the "bulk encryption devices" listed there,
I think it was the KG-84, was mentioned in a book about the ILLIAC IV
computer: such devices were hooked up to it because it was used for
some classified work (and that led to lamentable campus protests that
resulted in the machine being moved off-campus).
Also, Bruce's Applied Cryptography notes an NSA patent related to bulk
encryption, involving using multiple nonlinear functions of a single
shift register.
John Savard (don't snooze, don't snore)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
Date: Tue, 16 Nov 1999 17:25:17 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: more about the random number generator
Tom St Denis wrote:
> In article <80qrm0$bb1$[EMAIL PROTECTED]>,
> William Rowden <[EMAIL PROTECTED]> wrote:
> > The *cryptographic* security of a PRNG is generally described in
> > complexity-theoretic terms. My first question is therefore "What's
> the
> > algorithm?" Security relies on the presumed intractability of an
> > underlying number-theoretic problem.
> >
> > Nevertheless, statistical tests (e.g., FIPS 140-1) can be used in
> > security applications.
>
> Truly random generators should not have any theoretic explanation
> though. I mean I can explain why this rng works, but not predict the
> output without knowing all the nicks and nannies of the win32 task
> scheduler.
You and I may not know the nooks and crannies of the task scheduler, but
others might. While I doubt even Microsoft(tm) would claim to know all the
aspects of their product they and others certainly know enough to create a
task environment that is predictable. This is not hard to envision if you
consider ways to simplify the process hierarchy into one with predictable
behavior.
------------------------------
** 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
******************************