Cryptography-Digest Digest #965, Volume #8 Tue, 26 Jan 99 07:13:03 EST
Contents:
Re: Sanity check on authentication protocol (Antti Huima)
Re: S-box cycles ("Douglas A. Gwyn")
Re: Random numbers from a sound card? (Cuykens Anthony)
Re: Random numbers from a sound card? (Jon Haugsand)
Re: Random numbers from a sound card? (Nathan Kennedy)
Re: Random numbers from a sound card? (Nathan Kennedy)
Re: hardRandNumbGen ("burt")
Re: hardRandNumbGen (handWave)
Re: Who will win in AES contest ?? ("Sam Simpson")
Re: hardRandNumbGen (handWave)
Re: [req]:Cryptanalysis tool - word pattern table ([EMAIL PROTECTED])
Re: Help: Which secret key cipher? (Mok-Kong Shen)
Re: hardRandNumbGen (handWave)
Re: Pentium III... (Myself)
Re: Who will win in AES contest ??
----------------------------------------------------------------------------
From: Antti Huima <[EMAIL PROTECTED]>
Subject: Re: Sanity check on authentication protocol
Date: 26 Jan 1999 07:37:16 +0200
[EMAIL PROTECTED] (Edward Keyes) writes:
> In article <78hrtl$hqr$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
> > Depends how the shared-secret is generated. If it is derived from
> > a user-chosen password then it could be very bad indeed. Simply
> > because an offline dictionary attack could use this known plaintext
> > to verify guesses at the password (and we all know how bad most
> > passwords are). Bit interleaving won't help - the R_A will still
> > be identifiable.
> >
> > The only way I know of to make a key-exchange strong using a pre-arranged
> > (weak) shared-secret is with something like DH-EKE. The strength comes
> > from the fact that all message plaintext is uniformly random before
> > encryption is applied, and no plaintext is used twice, so there is nothing
> > to verify a password guess against. Unfortunately this uses DH so is no
> > good for your "computationally challenged" platform :-)
> >
> > It's an interesting problem though...
>
> Well, if my worst fear is a dictionary attack, then I'll be quite happy.
> Then I just have to make sure my keys are decent.
In article <[EMAIL PROTECTED]>, Antti Huima
<[EMAIL PROTECTED]> wrote:
> This protocol can be summarized as follows:
>
> A --> B: A, R_A
> B --> A: {K, R_A, R_B}_S
> A --> B: {R_B}_S
If you want to do better you could send in the second message HASH(S |
R_A) or something similar instead of R_A. Namely, you do not need to
send R_A, it is enough that Alice is able to verify that Bob knows it.
If you do it in some reasonable way like this, the known-plaintext
problem diminishes.
The other problem with this protocol is that you need to change the
shared secret often. Because the shared secret is used to encrypt
messages with some redundancy (e.g. the known R_A in the original
version), it is possible that the key used in the second and third
messages gets eventually cracked. At this point the cracker can
masquerade as the server as long as he wishes. To lessen this risk,
change the effective shared secret periodically. Here is one
suggestion to give an idea:
Let S_1 be a shared secret.
Add a nonce R_C that is sent in plain by B in the second message:
B --> A: {K, R_A, R_B}_S, R_C
User S = HASH(S_1|R_A|R_C) as the encryption key.
In this way, the encryption key will be every time different. Still,
only Bob and Alice can know it because it is derived from the "master"
shared secret S_1.
This adds one hashing to the protocol, plus increases bandwidth usage
with the length of R_C (e.g. 128 bits).
> At this point, I'm more concerned about making sure that there is no
> easy attack against the protocol. As was pointed out by another
> commenter, I do open myself up to a variant of a chosen-plaintext
> attack by allowing the client to choose R_A initially. I don't know
> exactly what possibilities that opens up, but it doesn't make me
> feel totally warm and fuzzy...
>
> Thanks, everyone. I think this needs some tweaking.
The chosen-plaintext attack can in bad circumstances used (as was
mentioned by another poster) to search for eligible values of K. Also,
it can in general be used to aid cryptanalysis. If you can remove
known plaintext without removing redundancy that will be good.
Remember to use e.g. the CBC mode of operation, and consider hashing
R_A.
--
Antti ([EMAIL PROTECTED])
* The blood of Christ cleanses from all sin. *
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: S-box cycles
Date: Tue, 26 Jan 1999 04:46:52 GMT
Anthony wrote:
> Could someone provide a definition of an S-box's "cycle length" please.
The smallest number (>= 1) of iterations of the S-box transformation
that reproduces the original input.
------------------------------
From: Cuykens Anthony <[EMAIL PROTECTED]>
Subject: Re: Random numbers from a sound card?
Date: Tue, 26 Jan 1999 09:41:42 +0100
Hi,
I do remember of a way a teacher told me to generate a "true" random
generator. You select some measurable information about your noise source (in
your case, lets says the frequence, the loudness, ...). Then you sample you
source at fixed interval and you check all your informations. For each coosen
information, if it is higher than the same info at the last sample, the output
is one, otherwize the result is zero. At each sample, this method will give you
one bit per criterion.
This is just an idea, what does guru think of it?
Nathan Kennedy wrote:
> David Ross wrote:
> >
> > Has anyone had success using a sound card (like a Sound Blaster) to
> > generate streams of random numbers?
>
> Sure. My favorite (T)RNG method.
>
> >
> > What sort of audio source would you suspect would be the best to use
> > in generating random numbers?
>
> I tune a cheap AM radio to a loud static channel, and wire that into the
> mic port.
>
> > How would you test the 'quality' of the generated random number
> > stream?
>
> Of course, you can't test the 'quality' by looking at the random numbers
> generated. You need to estimate the entropy of your source, and of course
> it's always going to be an estimate, you can almost never prove it.
>
> What I did, was compress it, multiply my hash size by the compression ratio
> by a fudge factor of 10. Then I would hash that much data, and assumed
> that the result was very close to 100% entropy. This is rather paranoid
> and slow though. If you don't need 100% entropy just go ahead and
> continually sample /dev/audio for data and use it as entropy for a PRNG,
> and sample the PRNG as often as you like. The quality should still be
> excellent... As long as you've got >128 bits of entropy total and the PRNG
> does its job, the result should be quite secure as long as nothing gets
> compromised.
>
> Nate
--
Anthony Cuykens
------------------------------
From: Jon Haugsand <[EMAIL PROTECTED]>
Subject: Re: Random numbers from a sound card?
Date: 26 Jan 1999 10:18:04 +0100
* Cuykens Anthony
| I do remember of a way a teacher told me to generate a "true" random
| generator. You select some measurable information about your noise source (in
| your case, lets says the frequence, the loudness, ...). Then you sample you
| source at fixed interval and you check all your informations. For each coosen
| information, if it is higher than the same info at the last sample, the output
| is one, otherwize the result is zero. At each sample, this method will give you
| one bit per criterion.
I am not sure that this will be random enough. I would guess that as
the number of concectutive ones increases, the probability to get a
zero the next time also increases. Better is to make two samples not
too close in time and output a one if the first is higher, and output
a zero if the second is higher.
Better still is to measure some quantity twice (e.g. sound level) and
use the least significant bit and output a one if you measure 10,
output a zero if you get 01. If you get 11 or 00, discard those.
--
Jon Haugsand
Norwegian Computing Center, <http://www.nr.no/engelsk/>
<mailto:[EMAIL PROTECTED]> Pho: +47 22852608 / +47 22852500,
Fax: +47 22697660, Pb 114 Blindern, N-0314 OSLO, Norway
------------------------------
From: Nathan Kennedy <[EMAIL PROTECTED]>
Subject: Re: Random numbers from a sound card?
Date: Tue, 26 Jan 1999 17:19:57 +0800
Cuykens Anthony wrote:
>
> Hi,
>
> I do remember of a way a teacher told me to generate a "true" random
> generator. You select some measurable information about your noise source (in
> your case, lets says the frequence, the loudness, ...). Then you sample you
> source at fixed interval and you check all your informations. For each coosen
> information, if it is higher than the same info at the last sample, the output
> is one, otherwize the result is zero. At each sample, this method will give you
> one bit per criterion.
>
> This is just an idea, what does guru think of it?
>
That's just one way of converting a raw sampled value into a bit stream...
It doesn't assure any randomness. It would probably be very predictable in
the short term, and likely biased as well.
Certainly, applying this to soundcard sampled data is little better than
the raw output of /dev/audio.
The best approach is not to waste any entropy, and just feed the raw data
to a hungry hash function, which will process it into an unbiased output.
The hash never has more entropy than what it is seeded with, however!
Bruce Schneier has an excellent paper on PRNGs on his site
(www.counterpane.com), which could serve as a good introduction.
Nate
------------------------------
From: Nathan Kennedy <[EMAIL PROTECTED]>
Subject: Re: Random numbers from a sound card?
Date: Tue, 26 Jan 1999 17:24:31 +0800
"R. Knauer" wrote:
>
> On Mon, 25 Jan 1999 20:11:33 +0100, Mok-Kong Shen
> <[EMAIL PROTECTED]> wrote:
>
> >> How would you test the 'quality' of the generated random number
> >> stream?
>
> >There are tests for statistical quality, e.g. Maurer's universal
> >statistical test. I am ignorant of tests for crypto quality.
>
> That's because there aren't any.
>
> It is a fundamental precept of crytpography that randomness is a
> property of how a number is generated, not a property of a number
> itself.
Absolutely. There's an excellent summation of a basic cryptographic idea.
That should be in the FAQ. (Probably is.) It can be extended beyond
randomness to apply to cryptographic strength in general in many cases.
Nate
--
Today's random number: 82
JTYLTK
------------------------------
From: "burt" <[EMAIL PROTECTED]>
Subject: Re: hardRandNumbGen
Date: Tue, 26 Jan 1999 09:33:00 -0000
Have you done any Frequency domain analysis on the signals produced?? any
periodicity in the frequency domain?
------------------------------
From: handWave <[EMAIL PROTECTED]>
Subject: Re: hardRandNumbGen
Date: Tue, 26 Jan 1999 02:46:01 -1000
burt wrote:
>
> Have you done any Frequency domain analysis on the signals produced?? any
> periodicity in the frequency domain?
Our team tested the hardRandNumbGen using a spectrum analyser during
1984. I do not have any photos of spectra available now, 15 years later,
because I resigned from that company many moons ago. We were looking for
radiated signals that could be picked up from outside the chip, and we
found a strong signal in the 500khz range, corresponding to the
oscillator used to sample the faster waveforms. There were other, weaker
frequencies detected, but I have no interesting facts to tell you about
the spectrum.
As I recall, the two faster oscillators ran at about 5Mhz to 50Mhz as
their frequencies were randomly modulated.
handWave
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: Who will win in AES contest ??
Date: Tue, 26 Jan 1999 10:48:51 -0000
Bruce Schneier wrote in message <[EMAIL PROTECTED]>...
>On Fri, 22 Jan 1999 10:32:03 -0000, "Sam Simpson"
><[EMAIL PROTECTED]> wrote:
>
>>
>>Robert Harley wrote in message ...
>>>
>>>[EMAIL PROTECTED] (Piotr Kulinski) writes:
>>>> What do you think who will win in AES contest ???
>>>> My type is Twofish....
>>>
>>>Why do you think it would be Twofish? Because Bruce Schneier wrote a
>>>very popular book? Twofish is quite a complex, non-obvious cypher.
>>
>>I thought TwoFish looked quite good from a conceptual point of view.
>>
>>I was surprised how much emphasis Bruce et al put on speed in respect of
>>TwoFish. If you look at his comments before AES:
>>
>>"This is serious business. Any algorithm proposed in 1997 won't be
approved
>>until at least 2000. It will be a standard for 20-30 years, in legacy
>>systems for at least another ten, securing data that might need to be
>>secured for another 20. This means we are trying to estimate security in
>>the year 2060. I can�t estimate security ten years from now, let alone
60.
>>The only wise option is to be very conservative."
>>
>>(1997/04/15 posting to sci.crypt)
>>
>>One would expect an ultra-conservative cipher, right?
>
>I thought Twofish was ultra conservative.
But Serpent is even more so, right?
Sam Simpson
Comms Analyst
-- http://www.hertreg.ac.uk/ss/ for ScramDisk hard-drive encryption & Delphi
Crypto Components. PGP Keys available at the same site.
------------------------------
From: handWave <[EMAIL PROTECTED]>
Subject: Re: hardRandNumbGen
Date: Tue, 26 Jan 1999 02:56:36 -1000
Medical Electronics Lab wrote:
>
> .���`�..���`�..���`�..���`�..���`�..���`�. wrote:
> [...]
> > Radioactive decay is also a large signal RNG. It may be considered
> > to be both digital and analog, as this RNG may be.
>
> It depends on how you measure it. Using a smoke detector it's
> a mighty damn weak signal. It takes about 1e5 amplification to
> see the radiation noise and that involves lots of shielding from
> outside sources as well as preventing feedback.
>
> It's not likely that anyone would stick a radiation source onto
> a processor either, so it has to be external. For the truely
> paranoid this is a good thing, they can look at their hardware
> and slap 'scopes on just to be sure everything is copasetic.
Radioactive sources occur in dynamic RAMs, which cause soft errors: LARGE
SIGNALS from thorium and uranium traces in common aluminum. Tim May
showed this around 1980. The problem is not putting radioactive materials
into chip, the problem is keeping them out. Special processing has
reduced this problem in recent decades. If you have a 1979 DRAM laying
around, it would be a slow source of random numbers as a Large Signal
Random Number Generator. This has been discussed before. Just write all
ones to the DRAM, observe the soft errors that cause zeros, and use the
address and time of the bit flipped to seed your hash.
Or take your smoke detector and place the vitals in contact with the
surface of a modern DRAM: Large Random Signals would result in the big
memory array. Take two and call me in the morning.
���`�..���`�..���`�..���`�..���`�..���`�. handWave
> > Thank you for this polite discussion.
>
> It has been fun reading, thank you too!
>
> Patience, persistence, truth,
> Dr. mike
You're welcome, God Bless You!
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: [req]:Cryptanalysis tool - word pattern table
Date: 26 Jan 1999 10:43:25 +0100
���� <[EMAIL PROTECTED]> writes:
> Greetings:
>
> Many years ago, I found a book in a library which at the time held no
> interest for me.
>
> It was nothing but a hugh table of letter patterns within English words.
>
> It would list, for example, a pattern such as "ABACD" and then every
> word in the English lang which fit that pattern (for the above example:
> "every" fits).
>
> As I said, at the time, I just thought it was an interesting curiousity.
> Now I realize that it would be a great tool for cryptanalysis of classic
> ciphers.
>
> Does anyone know where such a table can be obtained?
Write a program to generate the table? It should be straightforward to
write a mapping Word -> Signature and then enter them all into a table.
About 2 years ago a similar question (about "cryptogram pattern
matching") was posed in comp.lang.perl.misc. If you have a dictionary
of words (one word per line), the following Perl program will do the
job. Sorry about the terse code and the lack of comments; it was just
a quick hack.
die "Usage: $0 <pattern>\n" if @ARGV < 1;
$ARGV[0] =~ tr//a-zA-Z/d; # Delete non-letters
$ARGV[0] =~ tr/a-z/A-Z/; # Make only upper-case
# Build a regular expression from the pattern that will match the
# correct words
foreach (split(//, $ARGV[0])) {
if ($G{$_}) {
$RE .= "\\" . $G{$_};
} else {
$RE .= $N ? "(?!\\" . join("|\\",values(%G)) . ")(.)" : "(.)";
$G{$_} = ++$N;
}
}
open(DICT, "/usr/dict/words") or die "Cannot open dictionary\n";
while (<DICT>) {
print "$&\n" if /^$RE$/io;
}
Just my 50 �re,
Mats
--
Mats Kindahl, IAR Systems, Sweden
Any opinions expressed are my own, not my company's.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Help: Which secret key cipher?
Date: Tue, 26 Jan 1999 11:57:41 +0100
Trevor Jackson, III wrote:
>
> An OTP transmitted over a secure channel (courier or something similar)
> does not have to be proteced by more key material transmitted over the same
> channel. The "master key" I mentioned is a bad term. What I meant was a
> locally generated pad used to protect the stored copy of the communication
> pads. There is no reuse required because a new "storage key" (instead of
> master key) can be generated for each "comm key" received.
>
> I think Terry was concerned for the increase in risk of storing large
> quantities of key material for long periods of time; but he can address
Thanks for the clarification. Let me say what I believe I have
understood from above for the storage of the pad: Encrypt the pad
with a short key (by an algorithm of one's choice). On use, decrypt
it and then encrypt the unused part of the pad again with a new
short key. I believe this soft protection could be as effective as
the hard protection of putting the pad in a safe.
M. K. Shen
------------------------------
From: handWave <[EMAIL PROTECTED]>
Subject: Re: hardRandNumbGen
Date: Tue, 26 Jan 1999 03:24:11 -1000
Trevor Jackson, III wrote:
handWave wrote:
> > I am glad you raised the "handwaves" metaphore, because handwaves are
> > what toss coins. A complex person tosses a coin and you might think it
> > is random. The oscillator RNG in this discussion is directly analogous
> > to a coin toss in many ways. If a coin is not rotating (oscillating)
> > it will fall back into the hand in the same position that it stated from.
> > It is the rotation that helps the randomness, not only the complexity
> > of the nervous system, the elasticity of the skin, and the trembling of
> > the muscles. The rotation should be fast for best results. A juggler
> > could become skilled at non-random coin tosses for one coin that
> > rotates slowly. But if she tosses three coins with rapid rotation than
> > it is likely that random results will occur. If a periodic wind is
> > present in a coin toss, yes, it will influence the outcome, but the
> > result will often be recognizable as a useful random throw, or a throw
> > that was blown away. The same with this RNG.
>
> Human gestures are not a good foundation for system design. There are large,
> industrial concerns that rely upon human-gesture-generated unpredictability.
> Their interest is *not* statistical randomness as we find in simulations,
> games, and Monte Carlo tests (in spite of the latter name). Their interest
> is the same as ours: unpredicability. They are called casinos.
The product I designed was evaluated for casinos by Bally, a potential
customer.
>
> In spite of the fantastic efforts taken to eliminate predictability in games
> of chance human gestures can still dominate the outcomes completely. I'm not
> referring to shuffling cards systematically, but to rolling a roulette ball
> against the wheel so precisely that out of 20 tries a human can obtain a
> predicted outcome (slot 17) 10 times. 50% success. I think that constitutes
> predictability.
Yes, this is like the skilled juggler I described above. The analogy to a
hardRandNumbGen is a skilled hacker who controls the power supply noise,
the clock glitches, the radio beams so that the RNG becomes under his
control. The chip designer must anticipate such antics, and prepare the
module for lunar insertion.
> The hand-eye coordination involved is of an extreme level, requiring decades
> of practice to achieve. But it is real. The complexity of controlling a
> roulette wheel appears to me to be far larger than that of a coin toss. Even
> a fast one.
I dispute this. A coin has one bit of output, a wheel has many bits in
one toss. A wheel is a big target with a smaller bandwidth for RPMs. A
coin has a wider bandwidth, perhaps 1hz to 50 hz, a wheel, from .1 hz to
.5 hz on the initial spin. A coin may be tossed from a rooftop. Wheels
would fracture under such conditions.
>
> Without detailed scrutiny of your design I cannot tell whether it is robust.
I can send you the patent number by private email, upon request posted
here in sci.crypt.
> No inspection of the outcome will convince me it is. However, the design
> philosophy you have expressed leads me to believe there will be weaknesses in
> the system.
Yes there are weaknesses. A moonshot too has weaknesses, and people do
their best to prepare a module for its harsh environment. The payoff is
so sweet, though. It is better to have thrashed and lost some entropy,
than never to have thrashed at all.
>
> > The major source of randomness of this RNG is the unsynchronized
> > nature of multiple oscillators with randomly changing frequencies. This
> > is a large signal phenomenon, which cannot be accurately described
> > mathematically. Similar to a coin toss, many analog variables are
> > involved. These continuous variations of many influences cause seeming
> > randomness. If you can mathematically describe a human coin toss, then
> > so you can with this RNG. But you cannot, and I cannot. That does not
> > invalidate the usefulness of these seed generators, not in this
> > century.
>
> The phrase "randomly changing oscillators" is key to the paragrph above. I
> would like to question the use of the term random in the sense of
> unpredictable. Since the (intermediate) output of the system is driving the
> changes to the oscillators there is a full feedback loop present. This kind
> of system may pass statistical tests for randomness, but it may not be
> unpredictable. The result may "cause seeming randomness", but this is far
> from unpredictability. For instance, how much correlation would you expect
> from a set of such devices initialized identically?
We ran mathematical auto-correlation tests looking exactly for this, and
got good results. This type of multi-oscillator, frequency modulated,
unsynchronized circuit is part analog and part digits. It is susceptible
to realities as a hand exists in realities during a toss. Many subtle
influences come into play, including the capacitance between the moon and
the IC.
>
> Even the presmption that the output would pass statistical tests is
> questionable. One famous gafffe in PRNG design was Knuth's composite
> generator, which he called superrandom. Unfortunately it was a closed loop
> design.
It was a computer program.
>He did not forsee the possibility of cycles so short as to be
> degenerate. All closed loop designs contain this danger. If the hardware
> output is driving the hardware configuration, it is avidly searching for a
> configuration that represents a local minima in its volatility.
>
> Now, given initialization in a configuration near such a local minima, how
> much divergence would we find in the output of a set of these devices?
Good point. This is exactly what we were looking for. The results were
excellent. I wave my hands vigorously at this point to emphasize that
this type of circuit exists in the real world as we do. It is in the
school of hard knocks. It can be defeated. But it has some value as a
commodity product in certain well chosen scenarios.
handWave
------------------------------
From: [EMAIL PROTECTED] (Myself)
Subject: Re: Pentium III...
Date: Tue, 26 Jan 1999 11:36:51 GMT
On Thu, 21 Jan 1999 19:37:32 GMT, thermal and electromagnetic action
caused [EMAIL PROTECTED]'s brain to produce the following pseudorandom
thought:
>The OS is licensed to a specific machine, which might be interpreted as a
>specific processor.
And in reply, my brain hashed together this little bit of thoughtsum:
What do we do about multiprocessor machines?
-Myself-
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Who will win in AES contest ??
Date: 26 Jan 1999 12:14:10 GMT
On 25 Jan 1999 08:01:47 GMT, Serge Vaudenay <[EMAIL PROTECTED]> wrote:
[snip]
>
>One information which does not seem very popular is that DFC is still the
>fastest AES candidate on 64-bit microprocessors (much less than 300 cycles
>for one block encryption on EV6 which will run at 1GHz). It is the fastest
>on Alpha and TurboSparc. On Alpha EV56, there is a 1.5 speed ratio between
>DFC and the fastest AES candidates on 32-bit microprocessors (namely, RC6,
>Rijndael, Twofish). When the AES will be adopted, rare 32-bit microprocessors
>will survive. People says DFC has not enough rounds, which is why it is
>faster. Then increase it from 8 to 12 rounds, and it will be as fast as the
>popular ones!
>
i missed something... a dfc with 12 rounds is not faster on 64b cpu and
looses its speed advantage.
------------------------------
** 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
******************************
