Cryptography-Digest Digest #98, Volume #13 Sat, 4 Nov 00 17:13:00 EST
Contents:
Re: Known-plaintext attack on chaining modes (was Re: Give it up?) (SCOTT19U.ZIP_GUY)
Randomness from key presses and other user interaction (Mack)
Re: Rijndael question (SCOTT19U.ZIP_GUY)
Re: is NIST just nuts? ("Trevor L. Jackson, III")
Re: Hardware RNGs (Mack)
Re: Crypto Export Restrictions (David Schwartz)
Re: Randomness from key presses and other user interaction (David Schwartz)
Re: Hardware RNGs (David Schwartz)
Re: BENNY AND THE MTB? (Tim Tyler)
Re: Q: Computations in a Galois Field ("Brian Gladman")
Re: BENNY AND THE MTB? (Tim Tyler)
Re: hardware RNG's (Terry Ritter)
Re: RSA vs. Rabin (Francois Grieu)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Known-plaintext attack on chaining modes (was Re: Give it up?)
Date: 4 Nov 2000 20:21:45 GMT
[EMAIL PROTECTED] (David Hopwood) wrote in
<[EMAIL PROTECTED]>:
CUT
>
>It prevents a chosen-plaintext attack [*], but not known-plaintext.
>
>For full-feedback CFB,
> C[i] = P[i] XOR E[K](C[i-1])
> so (C[i-1], C[i] XOR P[i]) is a known plaintext/ciphertext (pt/ct)
> pair.
>
>For CBC,
> C[i] = E[K](P[i] XOR C[i-1])
> so (P[i] XOR C[i-1], C[i]) is a known pt/ct pair.
>
>For full-feedback OFB,
> S[i] = E[K](S[i-1])
> P[i] = C[i] XOR S[i]
> so (C[i-1] XOR P[i-1], C[i] XOR P[i]) is a known pt/ct pair.
>
>I.e. for each of these modes, having known message plaintext allows
>calculating pt/ct pairs for the underlying cipher (in the case of OFB,
>n+1 consecutive known message blocks are needed to find n pairs).
>
>
I think you covered all the basic approved 3 letter blessed
chaining modes. The above is the whole reason for my use of "Wrapped
PCBC" when one tries to attack scott16u or scott19u the attacker can
not get the "pt/ct" pairs. One could easily do the samething even
with Rijndael so that an attacker would not be able to obtain this
kind of information which should make it easier to break. But it would
slow the speed down but if one has some faith in Rijndael and wants
the "all or nothing property" and a lot more security it would not be that
hard to do. Even the use of the so called Slide Attack that MR Wagner
made was not even able to obtain these pairs in scott19u.
and it would not be able to obtain them from Rijndael if used instead
of the single cycle 19 bit look up table.
But do many really want encryption that is secure?
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Randomness from key presses and other user interaction
Date: 04 Nov 2000 20:39:33 GMT
There seems to be some argument as to whether timing
keystrokes is a good source of randomness.
So lets start a thread on that.
1) Key stroke timing is generally quantitized to about 20 ms
give or take.
2) The average typist doesn't get up to 90 wpm which assumes
6 keystrokes per word or there abouts. That is 540 keystrokes
per minute. Or 9 key strokes / second.
3) This gives an average of 5.5 quanta per keystroke.
4) Now our typist will may have some keystrokes that are 5 quanta
and some that are 6 quanta and some that are even more or less
5) this gives at MOST 1 bit per keystroke.
Now for the personal view.
I would say that it takes about 10 keystrokes to get 1 bit.
But that is still 54 bits/minute.
This isn't the best source of entropy.
Now this assumes a good typist. A bad typist tends to
make more erratic keystrokes and fewer keystrokes per
minute. So the best we can hope for is about 54 bits/min.
Now using Clock skew will probably generate a couple of
bits per minute. This estimate is much hard to pin down.
It depends greatly on the system. The entropy collected
is the acutal value of the clock skew. This will change with
time. Not a lot but enough that a couple of bits are available.
Long term collection of process timing is also capable of
generating entropy if the processes interact with humans.
In sum yes key press timings and mouse waggles can provide
entropy. PGP certainly uses it and hashes the data with a secure
hash.
But if you need a lot of randomness on a continuous basis it
is better to invest in a hardware RNG and then test its limits.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Rijndael question
Date: 4 Nov 2000 20:29:23 GMT
[EMAIL PROTECTED] (David Hopwood) wrote in
<[EMAIL PROTECTED]>:
snip
>David Hopwood <[EMAIL PROTECTED]>
>
>Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
>RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15
>01 Nothing in this message is intended to be legally binding. If I
>revoke a public key but refuse to specify why, it is because the private
>key has been seized under the Regulation of Investigatory Powers Act;
>see www.fipr.org/rip
>
David are you inviolation of the law be informing what your action
means. I thought if your key is seized you can't tell us that info
without being in violation of it.
Also what about your thoughts using a bijective implementation
of Rijndael so that if your are force to give a key. Give them one
that functions well but would be useless. I would appreicate your
thought on the subject.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
Date: Sat, 04 Nov 2000 15:44:37 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: is NIST just nuts?
Greggy wrote:
> > > : [Twofish] wasn't the most secure or had the most security margain
> > > : (Serpent wins that)
>
> But it is good enough that we intend to use it commercially...
>
> > > I think this is true if you assume that
> > > additional rounds beyond the best
> > > known attack result in more strength.
>
> But wouldn't you agree that your assumption is that we know the best
> known attack? While the NSA knows all we know, we know nothing that is
> secret to them. So extra rounds are called for (assuming that you want
> to hide your traffic from EVERYONE).
>
> > Yeah but the idea is that known attacks are used as a metric in the
> > absense of supreme enlightenment.
>
> I have shared such a story about a man of God who received the password
> for a UNIX account so that he could get on with completing his work and
> go home to his family before it got to be real late. It literally
> would have taken him many hours to track down the individual, but he
> simply asked God for help, and immediately he had the answer.
>
> Like the servant replying to the king who was warring against
> Israel, "No one here is against thee, but the Prophet of Israel tells
> the king of Israel what you say in your bedroom." When you have God on
> your side, you will win.
>
> I know. My God is faithful.
This last cannot be verified. Consider that the reporting statistics on
the Karnak Attack are wildly skewed. We can presume that almost every
successful attack will be reported, and almost none of the failed attempts
will be reported.
Thus it is possible (even common) for both sides to claim alliance with the
same Deity.
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Hardware RNGs
Date: 04 Nov 2000 20:54:13 GMT
>In article <[EMAIL PROTECTED]>,
> Paul Crowley <[EMAIL PROTECTED]> wrote:
>> Tom St Denis wrote:
>> > > then get your random bits from there. If you can make a half-
>decent
>> > > estimate of the entropy, you're away.
>> >
>> > You're assuming the stuff you feed Yarrow is random. Yarrow is a
>> > perfectly predictable PRNG otherwise :-)
>>
>> Well, if you correctly estimate the entropy of all of your sources as
>> zero, then you still won't get any biased or guessable bits from
>Yarrow
>> :-)
>
>
>You can never guess the bits from the RDTSC instruction.
>
>But I don't know why he would suggest Yarrow. The LSBs from the RDTSC
>are truly random in themselves.
>
The LSB of the RDTSC are purely deterministic. It increments one for each
clock tick. I may not be able to 'guess' the bits of the RDTSC but I can sure
calculate them. In a multi-process environment this is a bit more difficult
but
not impossible. It is effectively measuring the combined process run times.
>--
>I would prefer to live in a free society than
>a drug free society - even if the latter could
>actually be achieved.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,talk.politics.misc,alt.freespeech,alt.hacker
Subject: Re: Crypto Export Restrictions
Date: Sat, 04 Nov 2000 12:55:44 -0800
David Schwartz wrote:
> Yes, and that moment depends upon the phase relationship between the
> keyboard processor's clock and the CPU's clock. So long as those two
> clocks aren't produced by the same generator, that is truly random. Now
> there are some motherboards (more and more these days) where those two
> clocks come from the same generator. Even in those cases, a master clock
> is multiplied by a PLL (or similar device) to get the CPU clock, so
> there's still massive, unpredictable phase jitter between the two
> clocks.
Actually, I looked this one up. Pentium motherboards typically do work
the way I described. However, many newer motherboards have a crystal
oscillator, followed by a single PLL which produces the FSB frequency.
This FSB frequency drives the CPU clock multiplier (which is more
deterministic than a PLL) and is _divided_ to form the clock the
keyboard controller uses. This will result in much more deterministic
scan rates. This particular arrangement results in far less entropy from
keyboard time reads than you might expect.
Nevertheless, this limitation doesn't apply to TSC bits gathered from
events that are clocked independently. This includes data from disk and
network controllers. The exact frequency of the oscillators that run
those controllers measured by an independent oscillator has as much
entropy as the accuracy to which you can measure it.
DS
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Randomness from key presses and other user interaction
Date: Sat, 04 Nov 2000 12:56:53 -0800
Mack wrote:
>
> There seems to be some argument as to whether timing
> keystrokes is a good source of randomness.
>
> So lets start a thread on that.
>
> 1) Key stroke timing is generally quantitized to about 20 ms
> give or take.
It's the give or take in the 20 ms that contains the entropy. (At
least, for cases where the keyboard oscillator is taken directly from
the crystal or from a separate crystal. This does not apply for cases
where the keyboard clock is produced by dividing the FSB clock.)
DS
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Hardware RNGs
Date: Sat, 04 Nov 2000 13:01:49 -0800
Mack wrote:
> The LSB of the RDTSC are purely deterministic. It increments one for each
> clock tick. I may not be able to 'guess' the bits of the RDTSC but I can sure
> calculate them. In a multi-process environment this is a bit more difficult
> but
> not impossible. It is effectively measuring the combined process run times.
You can't calculate them because the number of clock cycles it takes to
do many things the CPU takes is non-deterministic. For example, I go to
read a block from a disk controller. Which CPU clock cycle that read
comes in at is non-deterministic because it relies upon the exact ratio
of two real numbers (the CPU oscillator and the disk controller
oscillator).
You would need to know an awful lot of internal timing data from the
computer that would normally be completely inaccessible to an attacker.
And, of course, any attempt you made to measure the disk controller's
performance would change the very numbers you are measuring. The net
result is that there is certainly no practical way and arugably no
conceivable way to predict the LSB of the TSC.
DS
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: BENNY AND THE MTB?
Reply-To: [EMAIL PROTECTED]
Date: Sat, 4 Nov 2000 21:02:23 GMT
Bryan Olson <[EMAIL PROTECTED]> wrote:
: Your description of how Matt's program behaves is not
: really accurate. [...] It never handles 128-bit granular files.
: [...] Matt could have taken the "finitely odd" stream from his
: compressor, mapped (bijectively) to 128-bit blocks, run
: Rijndael, then mapped to a byte stream. But that's not
: what he did. [...]
Yes, sorry. My description was speculation on how it /might/
work based on what little knowledge I had available.
The description in Matt's post in this forum on the subject was
indeed quite a bit different to what I had previously imagined.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Free gift.
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: Q: Computations in a Galois Field
Date: Sat, 4 Nov 2000 21:32:04 -0000
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:8tuqvv$icu$[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>,
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> >
> > Tom St Denis wrote:
> > >
> > > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > > >
> > > > Dumb question: For GF(2^m) with m sufficiently large, are
> > > > there specific tricks in programming that could speed up
> > > > multiplication/division? Thanks.
> > >
> > > I believe you meant GF(2)^m as in a polynomial basis with binary
> > > components. I keep getting mixed up with this as well (although
> people
> > > have explained it...)
> >
> > No. I mean exactly GF(2^m), the finite field of order 2^m
> > (a Galois field that is known to exist). I don't know
> > the mathematical object you referred to or its relationship
> > to GF(2^m).
>
> Um, cuz GF(p) is known as "a finite field with a prime p as a
> modulus". GF(2)^n refers to polynomials of degree 'n' with
> coefficients in GF(2).
No, he means GF(2^m), since GF(p^m), with p prime and m a positive integer,
is a finite field.
Brian Gladman
>
> Tom
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: BENNY AND THE MTB?
Reply-To: [EMAIL PROTECTED]
Date: Sat, 4 Nov 2000 21:17:08 GMT
Matt Timmermans <[EMAIL PROTECTED]> wrote:
: Cruel, Tim.
Sorry - no harm intended ;-)
[getting 8-bit files from streams?
: The arithmetic encoding page
: (http://www3.sympatico.ca/mtimmerm/biacode/biacode.html) did that pretty
: well, I thought [...]
Sorry - I'll try to ask a more specific question.
I was talking about how you feed the output of the arithmetic compressor
through Rijndael and wind up with an 8-bit granular file at the end.
I /think/ I understand (roughly) how this is done for the case where
the stream is longer than a block - but when it is smaller then a block,
we have:
``If a file has <= 128 significant bits [...] the 128 most significant
bits are encrypted with rijndael. This will typically result in a file
with 127 significant bits [...]''
What then? Is this where you apply a bijection between your finitely-odd
files and 8-bit granular files?
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Florist: Petal pusher.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: hardware RNG's
Date: Sat, 04 Nov 2000 21:56:26 GMT
On Sun, 05 Nov 2000 02:38:57 +0800, in
<[EMAIL PROTECTED]>, in sci.crypt Dido Sevilla
<[EMAIL PROTECTED]> wrote:
>I wonder why people have to be so paranoid regarding hardware RNG's to
>be used for cryptographic purposes. As long as there is reasonable
>shielding to keep egregious sources of non-randomness from overly
>biasing the noise generator circuit's input that should be good enough.
I think it mostly depends upon one's goals.
The idea that one could influence a semiconductor noise source yet
could not simply arrange within the computer to substitute PRNG data
for noise data does seem strange.
On the other hand, quantum noise is small. If not handled carefully,
it can be overwhelmed by other signals such as power supply hum or
switching noise, induced hum, RF signals, logic noise, etc. And if
such possibilities exist, we have a device for which there is a much
less direct argument for the signal being random.
>I'm just wondering how an electronic noise generator (such as one I've
>mentioned in a previous post that uses the base-emitter junctions of two
>transistors) could become maliciously biased by an attacker...
There are various ways of producing a small, analog, noise signal, and
a junction in breakdown is one way. The next step, though, is to
amplify and detect that noise for digital use. I have looked at many
ways to do that, and personally I favor the use of the PC sound card
for detection. This has the advantage of having been specifically
designed to digitize changing analog signals.
In contrast, trying to use digital latching (even implicitly, with
some form of PC input line), inevitably violates digital logic setup
and hold times, which can even, as in another recent discussion, cause
metastable operation. In general, the result is to induce a bias into
the digital data which the noise signal did not have. And that makes
it more difficult to validate the source of the noise.
>I'm a
>computer engineer by training and know a little of these things, and my
>understanding of the situation is that for some malicious person to bias
>a hardware RNG sufficiently he'd have to be able to bombard the area
>where the RNG is with significant quantities of RF radiation, enough
>that other electronic devices in the vicinity would receive noticeable
>quantities of interference as well (and wouldn't that make everyone
>suspicious?).
RF would be one way. Power supply variations would be another.
Temperature and radioactive flux should also have effects. But all
this seems lots more work than simply substituting pseudorandom data
(with a known pattern) for the actual noise data, inside the computer.
>Attempting to read out the results of the RNG seems to me
>a difficult task too, as how can the attacker be sure that the signal
>he's getting actually comes from the RNG and not from some other source
>of small-signal "random" electronic noise in the vicinity? In a typical
>locale there are lots of these!
There is something wrong with this logic! If various signals in the
area do affect the noise RNG, then our device is no longer based
solely on quantum effects. That is very dangerous because it means
that one of the other effects which it uses might be controlled,
perhaps fairly easily. I claim that what we want to do is to isolate
the noise signal from every other reasonable effect.
>People say it's not that simple to make a hardware RNG. Maybe so if
>you're going to use it to generate numbers for a national lottery or
>some other application where mathematically provable randomness is your
>goal. But for cryptography, I think it should be enough for a hardware
>RNG to be reasonably unbiased and impervious to manipulation and
>monitoring by malicious entities.
One could argue that since one does not know the intended use, one
should make the device as good as possible, even for cryptography.
But I think the issue is larger:
For cryptography, the whole point of building such a device would seem
to be to rely upon quantum events as opposed to the deterministic
events which dominate computing. I claim that it is important to be
able to identify a theoretical distribution in the noise source, so as
to be assured from whence this randomness comes. After that it will
need to be processed of course, but first we need to validate the
quantum nature of the source. Unless we can in practice measure a
theoretical distribution, then turn off the source and see massive
change, we don't have evidence which testifies that the source is
quantum and under our control.
>If an attacker can't actually bias
>the RNG in a useful way, or read the values it produces, then I guess
>that the RNG will not be a source of security problems. Of course, such
>raw random bits must be decorrelated and it would be far preferable to
>use the random bits only to seed a PRNG rather than be directly used.
Depending on what one needs the randomness for, I see no strength
advantage in using a deterministic system, for which we have no theory
of strength, instead of a quantum system, for which we do. There is a
speed advantage, but with that comes new risk.
Of course, a stream cipher would need to use some sort of complex PRNG
to produce identical results on each end. That PRNG might well be
seeded with a random message key value which is transported by a
master key or public key techniques.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: RSA vs. Rabin
Date: Sat, 04 Nov 2000 22:59:12 +0100
Fritz Schneider <[EMAIL PROTECTED]> pointed out
a scanned version of the the Jan 1979 Rabin paper online at
http://ncstrl.mit.edu/Dienst/UI/2.0/Describe/ncstrl.mit_lcs/MIT/LCS/TR-212
Thanks. If someone is interested, email me and I'll send a 674kB PDF
version with all the info in the 1.7MB ps file obtained from the above,
minus the better part of the scaning artifacts and comments.
The paper describes a public key scheme using the public transformation
x -> c = x(x+b) mod n
for n = p*q and some some public constant b, which can be 0.
Rabin points out the need of padding for signature applications:
"By convention, when whishing to sign a given message, M,
(the signer) P adds as suffix a word U of an agreed upon length k.
The choice of U is randomized each time a message is to be signed.
The signer now compresses M1 = MU by a hashing function to a word
C(M1) = c, so that as a binary number c<=n; (..) The computation of
C() is publicly known, so that c = C(M1) is checkable by everybody.
(..) Without the suffix, an adversary may attempt to feed to P
messages M for his signature, hoping to learn the factorization of
n from the solution of x(x+b) = C(M) mod n , which will be produced
by P as his signature. Actually, this does not seem to be a serious
threat because of the hashing effected by C(M)."
So Rabin actually describes padding, random padding; he proposes a
signature scheme with all the necessary security, and then some; he
proves security of the encryption scheme (not the signature scheme).
Great paper ! January 1979 !!
Francois Grieu
------------------------------
** 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
******************************
