Cryptography-Digest Digest #385, Volume #10 Sun, 10 Oct 99 19:13:03 EDT
Contents:
Re: Ritter's paper (Tim Tyler)
Re: RSA-512 Broken by Israelis (Tim Tyler)
Re: RSA-512 Broken by Israelis (Tim Tyler)
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column (Mok-Kong
Shen)
Re: Very well.. here's the article itself (was Re: Second "_NSAKey") (John Savard)
Re: Ritter's paper ("Trevor Jackson, III")
Re: Ritter's paper ("Trevor Jackson, III")
Re: Research paper... (Janusz A. Urbanowicz)
Re: Using PGP as a source of random numbers ("Kasper Pedersen")
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Ritter's paper
Reply-To: [EMAIL PROTECTED]
Date: Sun, 10 Oct 1999 17:07:44 GMT
Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
:> : PRNG-based ciphers are considered insecure for two reasons. 1) The potential
:> : unknown of the initial state is, in principle, reduced by half for each bit
:> : of output generated.
:> : 2) In practice, we have methods of detemining the initial
:> : state given the necessary number of bits of output, e.g., Berklecamp-Massey.
:>
:> So there's no such thing as a cryptographically-secure random number
:> generator?
: What definition are you using for cryptographically secure?
Well, /hopefully/ the same one that you're using when you are saying that
PRNG-based cyphers are "insecure". I'm talking about how easy they are
to break, relative to other cyphers.
:> Surely some generators are easier to crack than others... and some of them
:> are /extremely/ difficult to crack.
:>
:> I see no reason in principle why a PRNG-based cypher should be weak.
: In practice true, but getting less so as time goes on. In theory false.
Getting "less and less so as time goes on"? What support do you have for
this?
"In theory false"? How is a PRNG-based cypher any less secure than any
other type of cypher, in principle.
:> Certain PRNG-based stream cyphers have one or two problems associated with
:> the fact that they make no attempt to "smear" the information present in
:> each letter spatially across a number of letters in the cyphertext - but
:> this is not a weakness of using random numbers per se.
: The central point is that, in theory, any PRNG has a limited amount of
: state. As the PRNG operates it discloses that state. Once you have output
: >= state you can only have one possible state that generated that output.
...but how do you find out which one? *If* you have to search through the
whole period of the PRNG for the sequence, then this is directly analogous
to searching through the key-space of a block cypher.
: Finding the initial state given the output can be difficult in practice,
: but it cannot be made impossible.
Of course not. In the same sense that a brute force search through the
keyspace will "break" any cypher.
The point about a cryptographic RNG is that you can make it /very/ hard to
find short-cuts to kinding the key from the output. It's the same with
(e.g.) block cyphers - you can't make it impossible to find the key, but
you can make it very, very hard to locate it by methods more rapid than
searching the entire keyspace.
Your posts seem to paint a black picture of PRNG-based cryptography.
Looking more closely, I see absolutely no evidence that they
are (in principle) any less secure than any other modern cypher.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Marketing is sales with a college education.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: RSA-512 Broken by Israelis
Reply-To: [EMAIL PROTECTED]
Date: Sun, 10 Oct 1999 17:10:57 GMT
Patrick Juola <[EMAIL PROTECTED]> wrote:
: In article <7to0po$r13$[EMAIL PROTECTED]>,
: Bill Unruh <[EMAIL PROTECTED]> wrote:
:>In <[EMAIL PROTECTED]> Tim Tyler <[EMAIL PROTECTED]> writes:
:>>Quantum cryptography isn't /completely/ secure. It's just /arbitrarily/
:>>secure.
:>
:>>Reading the supposedly secure messages without discovery will always
:>>remain a *possibility*.
:>
:>Not sure what you mean by this. It is a theorem that you cannot clone a
:>quantum state. Ie, if you read it, you destroy it, and cannot copy or
:>recreate it.
: Yes, but if Eve can guess right.... perhaps by corrupting Bob's receiver
: so that she always picks the same quantum measurement to make that he
: does, perhaps by simply being damned lucky, she can still read
: the message.
*Exactly*.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Man who stands on toilet gets high on pot.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: RSA-512 Broken by Israelis
Reply-To: [EMAIL PROTECTED]
Date: Sun, 10 Oct 1999 17:18:06 GMT
Bill Unruh <[EMAIL PROTECTED]> wrote:
: In <[EMAIL PROTECTED]> Tim Tyler <[EMAIL PROTECTED]> writes:
:>Quantum cryptography isn't /completely/ secure. It's just /arbitrarily/
:>secure.
:>Reading the supposedly secure messages without discovery will always
:>remain a *possibility*.
: Not sure what you mean by this. It is a theorem that you cannot clone a
: quantum state.
You don't have to.
:>You can't even communicate at all using only quantum cryptography, if
:>someone insists on bugging the line. At least using public-key
:>cryptography, you can still talk to you friend reasonably securely if
:>someone is constantly listening in.
: Well, some might see this as an advantage. You will know immediately if
: someone is bugging the line. [...] I would think that know that you are
: being attacked is an advantage, not a disadvantage.
*Always* assume your messages are being intercepted. If not, there's
little point in using cryptography in the first place.
: IF (a big if) quantum computing becomes a reality, then you cannot use
: public key ( well at least not DH or RSA. Elyptic curves are probably
: still an open question) crypto at all securely. They quantum key
: exchange becomes the only secure way of exchanging keys over a potentially
: insecure line.
It appears very likely that quantum computers will be limited to a
certain number of qubits by the possibility of decoherence.
Kurzweil, in TAOSM, speculatively mentions a figure of 100 qubits.
AIUI, if you use this number of bits plus N - where N is the number of
bits you would normally use for security - for your public key, your
message is just as secure as they were before quantum computers were
invented.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
It is meaningless to speak of domesticating a child.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: Sun, 10 Oct 1999 18:11:10 +0200
Bruce Schneier wrote:
>
> The common thread through all of these exploits is that they've all
> pushed the envelope of what constitutes cryptanalysis by using
> out-of-band information to determine the keys. Before side-channel
> attacks, the open crypto community did not think about using
> information other than the plaintext and the ciphertext to attack
> algorithms. After the first paper, researchers began to look at
> invasive side channels, attacks based on introducing transient and
> permanent faults, and other side channels. Suddenly there was a whole
> new way to do cryptanalysis.
....................................
> Defending against these unknown attacks is impossible, but the risk
> can be mitigated with good system design. The mantra of any good
> security engineer is: "Security is a not a product, but a process."
> It's more than designing strong cryptography into a system; it's
> designing the entire system such that all security measures, including
> cryptography, work together. It's designing the entire system so that
> when the unexpected attack comes from nowhere, the system can be
> upgraded and resecured. It's never a matter of "if a security flaw is
> found," but "when a security flaw is found."
>
> This isn't a temporary problem. Cryptanalysts will forever be pushing
> the envelope of attacks. And whenever crypto is used to protect
> massive financial resources (especially with world-wide master keys),
> these violations of designers' assumptions can be expected to be used
> more aggressively by malicious attackers. As our society becomes more
> reliant on a digital infrastructure, the process of security must be
> designed in from the beginning.
I appreciate very much your arguments. I believe the above paragraphs
are entirely true and extremely valuable. I like only to mention that
some complementary and apparently also useful additional viewpoints
may be found in the following reference:
T. Ritter, Cryptography. IEEE Computer, Aug. 1999, p.94-95.
where, among others, the advantage of multiple encryption using
a number of (changing) ciphers is discussed. (This is an application
of the general principle of variability in my humble view.)
M. K. Shen
=============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: talk.politics.crypto
Subject: Re: Very well.. here's the article itself (was Re: Second "_NSAKey")
Date: Sun, 10 Oct 1999 17:52:53 GMT
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote, in part:
>[EMAIL PROTECTED] wrote:
>> ... but the magazine articles alleging active measures - based on the
>> experience of a Hagelin employee in Iran ...
>(Who by all accounts knew nothing about the alleged tampering.)
At the time, but supposedly he investigated afterwards and found out
about it.
>I didn't say "pin and lug machines". Some of the articles did state
>that the tampering inserted the key into the ciphertext stream. It
>would be hard to get away with that in a mechanical system, but I'm
>saying that even if it were electronic, such a claim is probably a
>distortion of the simple idea that ciphertext-only cryptanalysis is
>possible. News media are notorious for misunderstanding what is
>explained to them about technical matters and then reporting wrong
>information about such technical details.
That's entirely true. But my concern was simply that there seemed to
be a miscommunication between yourself and the previous poster
(Sundial Services) - you did appear to be saying that the allegations
concerned older machines, and when he stated that, no, the allegations
were about newer machines, you replied (as I understood it) that you
never claimed Crypto AG did not make any newer machines.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
Date: Sun, 10 Oct 1999 16:27:02 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Ritter's paper
Tim Tyler wrote:
> Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
> : Tim Tyler wrote:
> :> Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
> :> Surely some generators are easier to crack than others... and some of them
> :> are /extremely/ difficult to crack.
> :>
> :> I see no reason in principle why a PRNG-based cypher should be weak.
>
> : In practice true, but getting less so as time goes on. In theory false.
>
> Getting "less and less so as time goes on"? What support do you have for
> this?
In theory the initial state of a PRNG is completely determined by its output. Thus,
given a sufficiently sophisticated algorithm, one can infer the initial state from the
output. In the limit ones builds the "inverse machine", feeds it the output in
reverse chronological order, and produces the initial state.
As time goes on the sophistication of analytic algorithms increases whereas the
sophistication any particular PRNG is constant. Yes, you can increase PRNG
complexity, but it is not clear that that complexity makes the analytic task linearly
harder.
>
>
> "In theory false"? How is a PRNG-based cypher any less secure than any
> other type of cypher, in principle.
PRNGs are not less secure than small-key ciphers. They all have unknown strength or
strength relative to problems of unknown strength.
>
>
> :> Certain PRNG-based stream cyphers have one or two problems associated with
> :> the fact that they make no attempt to "smear" the information present in
> :> each letter spatially across a number of letters in the cyphertext - but
> :> this is not a weakness of using random numbers per se.
>
> : The central point is that, in theory, any PRNG has a limited amount of
> : state. As the PRNG operates it discloses that state. Once you have output
> : >= state you can only have one possible state that generated that output.
>
> ...but how do you find out which one? *If* you have to search through the
> whole period of the PRNG for the sequence, then this is directly analogous
> to searching through the key-space of a block cypher.
It depends on the structure of the RNG. For example, the Berklecamp-Massey algorithm
works on FSR generators.
>
>
> : Finding the initial state given the output can be difficult in practice,
> : but it cannot be made impossible.
>
> Of course not. In the same sense that a brute force search through the
> keyspace will "break" any cypher.
No, we're discounting brute force, otherwise we'd all settle for long keys. The
target is an algorithmic attacks such as differential, linear, slide, etc.
>
>
> The point about a cryptographic RNG is that you can make it /very/ hard to
> find short-cuts to kinding the key from the output. It's the same with
> (e.g.) block cyphers - you can't make it impossible to find the key, but
> you can make it very, very hard to locate it by methods more rapid than
> searching the entire keyspace.
How hard? To support your claim you need to show that there is a lower bound on the
work factor to find the initial state. Do you know of such a case?
>
>
> Your posts seem to paint a black picture of PRNG-based cryptography.
I used the word bleak.
>
>
> Looking more closely, I see absolutely no evidence that they
> are (in principle) any less secure than any other modern cypher.
Agreed.
------------------------------
Date: Sun, 10 Oct 1999 16:39:12 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Ritter's paper
Patrick Juola wrote:
> In article <[EMAIL PROTECTED]>,
> Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
> >Patrick Juola wrote:
> >
> >> In article <[EMAIL PROTECTED]>,
> >> Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
> >> >> : This does not lead to an engineering figure of merit, nor even to
> >> >> : scientific reproducibility.
> >> >>
> >> >> Indeed not. Do you have a metric which does to propose? If not I am
> >> >> liable to doubt that such a metric even exists.
> >> >
> >> >I do not. It appears to me that it may be possible to prove that such a metric
> >> >cannot exist. But right now the best I can do is mumble about negative
>information
> >> >space.
> >>
> >> I think that I would argue that any attempt to reduce "cypher strength"
> >> to a scalar quantity is ignorant and misguided. Differen cyphers
> >> have different areas of application, and different strengths depending
> >> on the use.
> >>
> >> One might as well try to come up with a metric for the best baseball
> >> player. Eventually it will come down to a question of how you compare
> >> pitchers to outfielders (or whatever).
> >
> >OK, there are separate application domains whose metrics will always be distinct.
>So
> >pick a single domain, without making it trivially small, and define a
>domain-specific
> >metric.
> >
> >Pitchers can be compared to pitchers along several (~10?) dimensions.
>
> ... at least. Which means that you can't even reliably identify the
> best pitcher, let alone the best ball-player. You can identify
> the best pitcher *along this dimension*, based on the assumption that
> the future will be like the past.
>
> Funny, that's exactly what modern cryptologists are doing when they
> start looking at things like key lengths and guessing how fast factoring
> algorithms will improve. You have no way to prove that I won't find
> an O(log n) factoring algorithm tomorrow -- but neither do you have
> any way of proving that the fourth-string pitcher for the Boise Hashbrowns
> won't suddenly find his groove and go 20-0 in the majors every season for
> the next ten years.
>
> >The permise does not appear to apply to cipher strength.
>
> Evidence? Pick any problem and it looks like there's reasonable evidence
> that our solutions are getting better, but not infinitely so.
I'll offer no evidence. My observation was based on the fact that progress both
flavors of
cryptology appears to be non-monotonic. The discontinuities make it very hard to use
past
experience to predict the future. There's a self-referential aspect to this in that it
calls for predictions of human ability. Can we predict genuis?
Could anyone have predicted the solution to the 4-color problem? Or the progress
toward
proving Fermat's Last Theorem?
I agree that there's evidence that suggests our modern cryptology is making progress,
but
there is no evidence that does more than suggest. And the threat of a discontinuity is
cipher strength is real.
Do you have any objective evidence that indicates we are getting closer to being able
to
measure cipher strength?
------------------------------
From: [EMAIL PROTECTED] (Janusz A. Urbanowicz)
Subject: Re: Research paper...
Date: 10 Oct 1999 19:45:38 +0200
[EMAIL PROTECTED] writes:
> I'm doing an extended essay (4000 words) for the IB program at my school
> (the IB program is advanced honors...kinda like AP, but a level higher),
> and I have decided on the topic:
> "The Effects of Cryptography in World War II"
>
> I have found a few good articles on the Enigma machine, but I am at a
> lack of books on the subject. Does anyone know of a good book that I
> can site for my essay? Also, any internet articles would be most
> apreciated.
Kozaczuk's "Enigma" - this may be a little hard to find but it is interesting.
Alex
--
* | Janusz A. "Alex" Urbanowicz, | DSS: 1024/0x21939169
--+~| | http://eris.phys.uni.torun.pl/~alex/ | D-H: 2048/0xA2E48564
\_|/ | "Historii nie mo�na tworzy�. |_ RSA: 512/0xAB425659
| | Mo�na jedynie mie� nadziej�, �e si� j� przetrwa." - G'Kar, Babylon 5
------------------------------
From: "Kasper Pedersen" <[EMAIL PROTECTED]>
Subject: Re: Using PGP as a source of random numbers
Date: Sun, 10 Oct 1999 17:41:35 +0200
<amadeus @0SPAM.netcomuk.co.uk (Jim Dunnett)> wrote in message
news:[EMAIL PROTECTED]...
> On Sat, 09 Oct 1999 13:49:40 GMT, [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
> wrote:
>
> > But it would be best ot get something based on some quantum effect like
> >radioactive decay or some other quatum measurment for true randomness.
>
> Radio noise/static is also useful for this.
Before I built a source, I used a soundcard and a radio (I just needed some
bits, I don't fancy OTPs). Unfortunately, radios are band-limited on the LF
side, and they have various other illnesses, seen from the number source
standpoint.
I'd recommend letting your computer sample at 16-bit mono 22kHz for 4 hours.
This gives you 340M words with 4 bits of entropy in each. Do this at least
four times, encrypt the files and XOR them togeather.
(The encryption step is to make the xor step efficient. If you just XOR 2
plain audio files, you gain only 1 bit)
Of course, this means having your PC sampling for 16 hours for each CD you
want to create, but it's as good as it gets.
The only thing that could be questioned is how many bits the radio delivers
per sample. If you are paranoid, use a larger number of runs.
/Kasper
------------------------------
** 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
******************************
