Cryptography-Digest Digest #460, Volume #9 Sat, 24 Apr 99 19:13:04 EDT
Contents:
Wie �ffne ich PGPdisk ohne Pa�wort? ("Michael")
Re: Rijndael (Matthias Bruestle)
Re: choosing g in DH (D. J. Bernstein)
Re: Radiation/Random Number question ([EMAIL PROTECTED])
Re: Radiation/Random Number question ([EMAIL PROTECTED])
Re: How do I open PGPdisk without password? (Peter Gunn)
Re: May be wrong place to ask this... (RDJ)
Re: FSE-6 Report: Slide Attack (James Frey)
Re: True Randomness & The Law Of Large Numbers ("Douglas A. Gwyn")
Re: Radiation/Random Number question (Jim Dunnett)
Re: Prime Numbers Generator ("Trevor Jackson, III")
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
----------------------------------------------------------------------------
From: "Michael" <[EMAIL PROTECTED]>
Subject: Wie �ffne ich PGPdisk ohne Pa�wort?
Date: Sat, 24 Apr 1999 16:23:55 +0200
Ich habe mich bei der Eingabe eines PGPdisk Passwortes wohl vertippt und
kann nun die Datei nicht mehr �ffnen. Gib es ein Programm, das einig
Passworter ausprobiert, die ich eingeben kann(so wie crack)?
Is a programm like crack availabel for PGPdisk???
------------------------------
From: [EMAIL PROTECTED] (Matthias Bruestle)
Subject: Re: Rijndael
Date: Sat, 24 Apr 1999 16:08:46 GMT
Mahlzeit
Maybe they should have choosen a Gaellic word.
Mahlzeit
endergone Zwiebeltuete
--
PGP: SIG:C379A331 ENC:F47FA83D I LOVE MY PDP-11/34A, M70 and MicroVAXII!
--
...the Mouse That Roars, the Crew of the Flying Saucer, the
Magnificent Ambersons, the House I Live In, the Sound of One Hand, the
Territorial Imperative, the Druids of Stonehenge, the Heads of Easter
Island, the Lost Continent of Mu, Bugs Bunny and His Fourteen Carrots...
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Subject: Re: choosing g in DH
Date: 24 Apr 1999 18:25:26 GMT
Let's say you have a generator g and a private exponent s. Anyone can
take your public key g^s to the (p-1)/2 power to obtain g^(s(p-1)/2),
which is (-1)^(s mod 2). In short, the bottom bit of s is public.
So you lose nothing by always choosing s to be an even number, say 2t.
Now there's no difference between base g and base -g; your public key is
(-g)^(2t), and if somebody else has private exponent b then your shared
secret is ((-g)^b)^(2t).
When (p-1)/2 is prime, any number mod p other than 0, 1, -1 is either a
generator or a square. The squares are the negatives of the generators.
I choose square bases; then the same code can be reused in certain other
protocols that require square bases and allow odd exponents. Base 2^32
is particularly convenient for typical multiprecision code.
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
> That makes no sense. If you know a generator g in which you can
> compute discrete logs, then you can compute discrete logs in any base.
Conversely, if you can compute discrete logs base 2^32, then you can
compute discrete logs base g, for any generator g, if (p-1)/2 is prime.
But it's a bit easier to compute _small_ discrete logs base g than to
compute _small_ discrete logs base 2^32.
---Dan
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Radiation/Random Number question
Date: Sat, 24 Apr 1999 18:34:28 GMT
In article <[EMAIL PROTECTED]>,
Medical Electronics Lab <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> > Can you use an ac-coupled soundcard as your acquisition system?
>
> Sure. You'd only have to make sure the soundcard is reasonably
> shielded from the system noise and that's easy to measure. I suspect
> it would work quite well.
Hmmm. Your paper describes a gain of a million -a sound card microphone
preamp can't do that, I think. Your circuit is a very well shielded
multistage lab/instrumentation amplifier, with some digital stuff on the
outputs. When I've tried to use my soundcard as an audio-rate 'scope, I notice
limited gain problems with small signals. FWIW.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Radiation/Random Number question
Date: Sat, 24 Apr 1999 18:29:02 GMT
In article <[EMAIL PROTECTED]>,
Jim Dunnett wrote:
> On Tue, 20 Apr 1999 17:58:40 GMT, [EMAIL PROTECTED] wrote:
>
> >Use a sound card to acquire FM hiss, and distill it
>
> Any thoughts on using an FM radio with a shielded dummy
> antenna for your hiss?
Yes, this works fine, even in the EMI environment of a computer.
The point is that you have a 'secret' local reception-environment
(and 'secret' internal amplifier noise) which gives you real
entropy.
Of course, a certain amount of distillation (ie, compression) will be
necessary. But you can measure this (e.g., Maurer's universal statistical
test) and tell when you've boiled off all the redundancy.
I've done this with 1. a $10 radio-shit mono FM radio, with antenna removed,
fed into a soundcard 2. an internal TV/FM receiver card.
In other words:
capture rawhiss.wav. Run MUST on it: you measure say 2.5 of 7.18.
Now distill this: for every 2 bits of rawhiss.wav, output 1 bit, the
xor of the two. Measure the result with MUST again: the entropy score will go
up.
Run your distiller again with a higher compression, e.g., taking the
xor (aka parity) of 4 bits. The MUST score will be higher.
When the entropy asymptotes at the expected value (7.18 for MUST with
a byte-size block) you can burn your OTP. You can whiten the distilled
entropy by passing it through a secure-hash, but this won't be necessary
if you get your MUST score up there.
======
"He saying there are dangerous nuts out there, me saying
you bet, and the most dangerous are officials." ---John Young
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
Date: Sat, 24 Apr 1999 19:46:52 +0100
From: Peter Gunn <[EMAIL PROTECTED]>
Subject: Re: How do I open PGPdisk without password?
Sie k�nnen diese Meldung zum Deutschen �bersetzen,
indem Sie zum folgenden URL gehen:-
http://babelfish.altavista.digital.com
Nope, there isnt a (feasible) general purpose crack. There would
be a riot if there was :-)
ttfn
PG.
Michael wrote:
> Ich habe mich bei der Eingabe eines PGPdisk Passwortes wohl vertippt und
> kann nun die Datei nicht mehr �ffnen. Gib es ein Programm, das einig
> Passworter ausprobiert, die ich eingeben kann(so wie crack)?
>
> Is a programm like crack availabel for PGPdisk???
------------------------------
From: (RDJ)
Subject: Re: May be wrong place to ask this...
Date: Sat, 24 Apr 1999 19:17:14 GMT
On Fri, 23 Apr 1999 21:23:41 -0700, Bob Novell
<[EMAIL PROTECTED]> wrote:
>I located a site with links to some of the source from the Applied
>Cryptography book, but many are tar.gz and c.gz files.
>
>Being a DOS/Windows user, I don't know how to unarchive these files.
>
>Can anyone point me in the direction of a utility or such that will
>handle these files.
>
>The site I found is:
>http://website-1.openmarket.com/techinfo/applied.htm
You could probobly find just an archiving utility, but if you get
Windows Commander (shareware), it treats archives like directories.
It's one of the most useful programs out there and I recommend it
highly. (This is an unpaid, unsolicited endorsement. I just like the
program) You can find it at http://www.ghisler.com. The shareware
version is free and fully functional, with one quite tolerable pop-up
plug at startup.
------------------------------
From: James Frey <[EMAIL PROTECTED]>
Subject: Re: FSE-6 Report: Slide Attack
Date: Tue, 20 Apr 1999 08:03:38 -1000
[EMAIL PROTECTED] wrote:
>
> > The analyst does not have access to the inner workings
> > of
> You mentioned round. Does it use the input/output or the inner workings?
> (One or the other!)
It uses in input and output. By sliding a plaintext by one round
the inner part of one encryption can be Considered. We do not
alwaysknow what happens after one round but we can Consider the
logic of one WEAK round, (like DES) to definitively and unambiguously
decide whether one known plaintext P0' can appear inside the cipher
one round past another plaintext P0. The key can be calculated
if the input to a round and the output from a round are known.
If the slid input plaintexts AND the slid output ciphertexts are
consistent with the digital logic of the WEAK round function
then one can recover the round key bit common between the two.
> Why would you comprea F(P)=P' Wouldn't you want to compare matching pairs of
> ciphertext/plaintext? Is there any known correlation between subsequent
> blocks?
By coincidence, F(P) will sometimes generate a code equal to P'.
The birthday paradox for DES makes this happen every 2^33 plaintexts.
>
> >
> > Example: you are cracking DES and you have 5 billion
> > pairs of ciphertext blocks and the matching plaintext
> > blocks. Take the first plaintext and the second plaintext.
> > Using digital logic decide whether you could encrypt the first
> > plaintext with a key to get the second plaintext, which is a
> > key that is consistent with the two matching slid ciphertexts.
> > If logic shows that it cannot be done, then move on to the third
> > plaintext. After a candidate slid pair is found, calculate any keys
> > that makes it logically correct. Try that key on other pairs
> > to confirm. One success will obtain some key bits, more bits can
> > be obtained by more work on inner rounds, depending on the key
> > schedule.
>
> Ah, but finding a key knowing only that F(P)=C is rather hard for most
> ciphers.
>
> Again you mention inner rounds, does this attack the output/input or the
> cipher?
>
> Tom
For some ciphers it is feasible. These are the vulnerable ciphers.
A single round is seldom intended to provide security. That is why
the Slide Attack threatens many modern ciphers.
> -----------== Posted via Deja News, The Discussion Network ==----------
> http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Sat, 24 Apr 1999 19:50:57 GMT
"R. Knauer" wrote:
> >Just looking at the connections etc. does not entitle one to
> >pronounce that it *has* to be working right.
> I never claimed that. You are erecting another straw man.
> ...
> You must run diagnostics and let them tell you the condition of the
> subsystems. If all subsystems are performing within specification,
> then by definition the overall system is performing within
> specification - and there is nothing to be suspicious about.
Sure *sounds* like such a claim about the connections etc.
> To make the final decision whether the TRNG is malfunctioning or
> not, I would have to run diagnostics on each subsystem. If those
> subsystems perform within specification, then the TRNG is not
> malfunctioning even if one of its output sequences fails a
> standard statistical test.
What sort of subsystem diagnostics, then? At some level, you
have to attain sufficient confidence in the operation of some
assembly of physical components that can be affected by a
variety of environmental factors. (I told you guys the story
about the M�ssbauer data and the putative critical-point fine
structure. There was a case where every piece of the system
had been carefully designed, assembled, and calibrated, yet
the "output" had a periodic bias.) The confidence one has in
the overall operation-to-spec of the system is a function of
the confidence one has in the operation-to-spec of the
subsystems, which in turn depends on the confidence instilled
by the diagnostics. This is statistical from top to bottom.
> One thing you seem not to realize is that all possible sequences
> exist in an infinitely long random number, ...
To the contrary, I realize that that isn't germane. You don't
have an "infinitely long random number" (actually sequence),
you have whatever the particular realization of an intended
TRNG produces, and that output might be far from random *for
causal reasons*, not only due to the "luck of the draw".
> Nobody on your side of this debate has offered one rational
> argument why such "failed" sequences cannot exist for true
> random processes.
That's not surprising, since nobody "on my side of the debate"
believes that in the first place. Highly ordered sequences
can indeed exist even if such a generator is functioning
correctly, but they are *less probable* than less-ordered
sequences (where "ordered" means the property we test by some
standard method). Tests for order provide evidence for or
against the hypothesis of correct functioning, and if we
accrue sufficient *weight* of evidence against the hypothesis,
it could outweigh whatever a priori confidence we might have
had in the hypothesis (standard Bayesian/likelihood stuff).
To argue otherwise amounts to saying that no amount of factual
evidence can cause one to alter his belief, which is why I
earlier labeled such a belief "mystical".
> If a radioactive TRNG happened to output a sequence of 20,000
> bits which failed the FIPS-140 Monobit Test, are you prepared
> to declare that radioactive decay is no longer a true random
> process?
Of course not, but what I am prepared to declare is that if
your specific instance of a putative TRNG consistently fails
such tests, my confidence in its correct operation plummets
accordingly. I'm going to base my final decision on whether
or not its output is suitable for my application (OTP key
generation, perhaps) on the basis of the way that the actual
evidence *modifies* my *initial* expectation that the gizmo
should produce a suitable sequence.
Of course, if you don't bother to *collect* any evidence,
your a priori assumption of correct device operation will
never change, but that doesn't alter the fact that it is
truly broken, nor that an opponent might be able to exploit
that property if you use it to generate key streams.
Note, we're not saying that the testing would be against the
theoretical *design*, which one might well have confidence
should produce sufficiently random output, but rather against
an actual *realization* (concrete instance) of the design.
I *have* in fact seen genuine patterns in data that was
"supposed to" be random noise. Many times. Why would
your TRNG be any different?
------------------------------
From: [EMAIL PROTECTED] (Jim Dunnett)
Subject: Re: Radiation/Random Number question
Date: Sat, 24 Apr 1999 19:55:45 GMT
Reply-To: Jim Dunnett
On Sat, 24 Apr 1999 18:29:02 GMT, [EMAIL PROTECTED] wrote:
>In article <[EMAIL PROTECTED]>,
> Jim Dunnett wrote:
>> On Tue, 20 Apr 1999 17:58:40 GMT, [EMAIL PROTECTED] wrote:
>>
>> >Use a sound card to acquire FM hiss, and distill it
>>
>> Any thoughts on using an FM radio with a shielded dummy
>> antenna for your hiss?
>
>Yes, this works fine, even in the EMI environment of a computer.
>The point is that you have a 'secret' local reception-environment
>(and 'secret' internal amplifier noise) which gives you real
>entropy.
[detail snipped]
Very good. Thank you. I've archived that.
I'd use an amateur radio rig as the screening is
better. Just removing the antenna will allow quite a
lot of outside (non-random) noise in.
I must look for MUST. I only have 'ENT' and another
more recent entropy comparison program.
Thanks again.
--
Regards, Jim. | The comfortable estate of widowhood is
olympus%jimdee.prestel.co.uk | the only hope that keeps up a wife's
dynastic%cwcom.net | spirits.
marula%zdnetmail.com | - John Gay 1685 - 1732
Pgp key: pgpkeys.mit.edu:11371
------------------------------
Date: Sun, 25 Apr 1999 05:38:06 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers Generator
David Kuestler wrote:
>
> Mok-Kong Shen wrote:
>
> > Trevor Jackson, III wrote:
> > >
> > > On a lark I launched the program mentioned below on a medium sized
> > > workstation (details below). It has been running for over 70 wall-clock
> > > hours getting 35 hours of CPU time. Since the algorithms appear to be
> > > disk-intensive, the 50% fraction could be right. Very little else has
> > > been running on the machine because the progam is barely nice.
> > >
> > > However, the fact that the output files is at 861 MB, well over the
> > > final size expected give me some pause. I suspect something is wrong.
> >
> > I don't know why people need a big bunch of not too large primes as
> > currently being described. More likely for practical computation is
> > that one needs individual primes. The computer algebra system
> > Mathematica is very fast in providing the n-th prime for fairly large n.
> >
> > M. K. Shen
>
> I have some algorithms that use sets of 64 bit primes of specified numbers of
> bits ( eg. all 64 bit primes with 3 bits ).
> To generate a set of primes I find it most efficient to generate the set of
> all numbers with the specified number of bits, then in a single pass of an
> 800Mb 32bit prime file, discard non primes.
>
> If you have a more efficient method I would be very very interested, as some
> of my set generations take weeks : -{
You may want to look at probabalistic primality tests. I think the
Miller-Rabin (if I got the names right) test is one of the fastest
currently. I believe you can find this used in PGP.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Sat, 24 Apr 1999 20:45:05 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 24 Apr 1999 19:50:57 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>What sort of subsystem diagnostics, then?
The kind one would perform on a piece of scientific equipment.
>(I told you guys the story
>about the M�ssbauer data and the putative critical-point fine
>structure. There was a case where every piece of the system
>had been carefully designed, assembled, and calibrated, yet
>the "output" had a periodic bias.)
Apparently someone goofed. I trust we are not wringing our hands over
human error.
>The confidence one has in
>the overall operation-to-spec of the system is a function of
>the confidence one has in the operation-to-spec of the
>subsystems, which in turn depends on the confidence instilled
>by the diagnostics. This is statistical from top to bottom.
I never claimed that statistics is invalid when applied to the
subsystems. I only claimed that statistics is invalid when applied to
the output sequences, and then only for a certain kind of test under a
kind of certain condition.
But just because I recognize the validity of statistical measurements
in general does not mean I am willing to accept their validity in all
instances. The attempt to determine non-randomness from the sequence
itself is not the same as attempting to determine the proper operation
of some process by direct measurement. The reason for that is that
true randomness is not a property of the sequence itself, but a
property of the overall TRNG. To demonstrate that the overall TRNG is
not random, you must inspect each of its subsystems and not its
output.
>That's not surprising, since nobody "on my side of the debate"
>believes that in the first place.
That is not an accurate characterization of your side of the debate
for all people concerned. Some people are still convinced that the
FIPS-140 suite of tests is valid, namely if the Monobit Test is failed
then the TRNG is not random.
One of the questions that needs to be asked is this: If the Monobit
Test is passed for one value of bias, and is failed for another value,
then what is the mechanism for the TRNG going from good to bad on the
basis of one 1 bit? It's as if one lousy extra 1 bit ruined the whole
TRNG.
>Highly ordered sequences
>can indeed exist even if such a generator is functioning
>correctly, but they are *less probable* than less-ordered
>sequences (where "ordered" means the property we test by some
>standard method).
That is a correct statement. Now let's apply it to the FIPS-140
Monobit Test. According to that document, you are to generate one
contiguous sequence of 20,000 bits, count the number of 1 bits and
from that infer whether the TRNG is broken. If the number of 1 bits is
excessive or deficient by a stated amount, then you are to conclude
without further investigation that the TRNG is indeed broken.
If you don't believe me, read it for yourself:
http://csrc.ncsl.nist.gov/fips/fips1401.htm
But I do not buy any of that nonsense. I know better than to sucker
for something so simplistic as a single small sample test of 1-bit
bias. You can wave all the statistics books at me that you want, but I
am not going to drink that snake oil - certainly not after reading Li
& Vitanyi and Feller and seeing all those examples where statistical
tests are completely invalid.
>Tests for order provide evidence for or
>against the hypothesis of correct functioning, and if we
>accrue sufficient *weight* of evidence against the hypothesis,
>it could outweigh whatever a priori confidence we might have
>had in the hypothesis (standard Bayesian/likelihood stuff).
My claim is that you must conduct a large number of tests using very
large samples in order to get the weight of evidence on your side. A
single application of a simplistic test like the FIPS-140 Monobit Test
using a mere 20,000 bits is NOT enough evidence to come to the
conclusion that the TRNG is malfunctioning.
>To argue otherwise amounts to saying that no amount of factual
>evidence can cause one to alter his belief, which is why I
>earlier labeled such a belief "mystical".
Whatever. <jeez>
You sure do like those straw men of yours, don't you.
>Of course not, but what I am prepared to declare is that if
>your specific instance of a putative TRNG consistently fails
>such tests, my confidence in its correct operation plummets
>accordingly.
Fails WHAT tests? The FIPS-140 Monobit Test?
Define "consistently" in analytic terms.
And who cares about "confidence"? I want "reasonable certainty", the
kind demanded in peer-reviewed journals.
You cannot just assert that you are "confident" about your results -
you have to demonstrate reasonable certainty.
>I'm going to base my final decision on whether
>or not its output is suitable for my application (OTP key
>generation, perhaps)
That has always been the benchmark application. If a keystream is
suitable for use with the OTP system, then that is prima facie
evidence that it was produced by a TRNG. The problem is, however, that
there are no analytical tests to prove that the keystream is suitable
for the OTP system.
>on the basis of the way that the actual
>evidence *modifies* my *initial* expectation that the gizmo
>should produce a suitable sequence.
Define "suitable" in analytic terms.
>Note, we're not saying that the testing would be against the
>theoretical *design*, which one might well have confidence
>should produce sufficiently random output, but rather against
>an actual *realization* (concrete instance) of the design.
Actually in the case of the radioactive TRNG they can work together.
For example, one way to certify that the source-detector subsystem is
working correctly is to measure the decay of the radioactive sample.
If it behaves in a certain way, you take that as evidence that it is
truly random.
For example, you could measure the Mossbauer Effect spectrum (at least
in principle) and see if the lineshape is Lorentzian, which is strong
evidence that the subsystem is working properly - and also confirms
that the process is random, since a Lorentzian lineshape is what you
expect for random spontaneous emission.
You could also measure the decay profile over time and see if it is a
simple exponential, which also is what you would expect for a random
process. In fact, if you have both the linewidth and the decay
constant, they are related, so even that can be checked.
>I *have* in fact seen genuine patterns in data that was
>"supposed to" be random noise. Many times. Why would
>your TRNG be any different?
Two reasons:
1) The source of randomness is based on a true random quantum process,
which is verified by direct measurement as outlined above.
2) The TRNG subsystems are shown experimentally to operate within
specifications.
What reason can you give for why you think the output is NOT random,
assuming those two criteria above are met?
But all this is not necessary, since once a quantum computer is built
it can be programmed with the algorithm for true randomness (which is
already known) and the numbers that are calculated must be truly
random - or otherwise the quantum computer is broken, in which case it
won't computing anything.
Bob Knauer
"As nightfall does not come at once, neither does oppression. In both
instances, there's a twilight where everything remains seemingly unchanged,
and it is in such twilight that we must be aware of change in the air,
however slight, lest we become unwitting victims of the darkness."
-- Supreme Court Justice William O. Douglas
------------------------------
** 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
******************************
