Cryptography-Digest Digest #172, Volume #9 Tue, 2 Mar 99 03:13:03 EST
Contents:
Re: One-Time-Pad program for Win85/98 or DOS ("arcmight")
Re: My Book "The Unknowable" (Terry Ritter)
Re: paper on all 15 AES candidates ?? (Bill Unruh)
Re: True Randomness - DOES NOT EXIST!!! (BORIS KAZAK)
Re: One-Time-Pad program for Win85/98 or DOS (Sorcerer)
Re: Musings on the PKZip stream-cipher (Terry Ritter)
Re: Musings on the PKZip stream-cipher (Anthony Naggs)
Re: Hardware Random Numbers: Not an *explicit* feature (Terry Ritter)
Re: Define Randomness (Terry Ritter)
Re: A New Public-Key Cryptosystem (Lowball61)
----------------------------------------------------------------------------
From: "arcmight" <[EMAIL PROTECTED]>
Subject: Re: One-Time-Pad program for Win85/98 or DOS
Date: Mon, 1 Mar 1999 22:31:11 -0800
Crossposted-To: alt.security,alt.privacy
"... And now for the prosecution, the government will introduce evidence
that the defendant, having used
an insecure implementation of the one-time pad, which has been broken and
reveals the true intent of the defendant,
The cryptographic String:
axka03in3nc9-085na;n/-0937ugh2wn3rtk.w9u23-9asfjW'NRF-0348u3425834250mnsdf/.
n,zxcv84tasdfadsf
Translates to:
Bomb at midnite, death to all facists, burn the banks, loot and rape, long
live the revolution
For which under the Anti-Terrorism act of 1996 et al., we hereby request the
death penalty...."
< The unfortunate problem with one-time pads is that the government can have
them say anything they want
when they prosecute you, and how you gonna prove it's anything else? Given
the fact that justice in america is a tennis game with your ass the ball,
you think you WON'T be entrapped??? right! >
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Crossposted-To: sci.math,sci.physics,sci.logic
Subject: Re: My Book "The Unknowable"
Date: Tue, 02 Mar 1999 06:55:54 GMT
On Tue, 02 Mar 1999 01:29:04 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (R. Knauer) wrote:
>On Mon, 01 Mar 1999 22:54:24 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>
>>The bias-removing CRC transformation is linear and thus reversible.
>
>I thought that the CRC would also remove correlations, by "hashing" or
>scambling the data.
I see correlations as a form of statistical bias: The implication of a
correlation is that some particular sequence (possibly of length 1)
produces a non-flat or "biased" probability distribution for a
subsequent sequence.
As long as we put in substantially more "entropy" data than we take as
result, the CRC values should have a flat distribution. But if a
correlation exists of such a nature that it greatly reduces the
entropy into a subsequent CRC computation, that might affect the
results. We seek to avoid this by having a substantial excess of
entropy (much more input than output).
And CRC is not magic: If we send the same data in, we should expect
the same CRC (or same change in CRC) as a result. The input data must
have independence.
>Is the CRC, properly implemented, capable of removing significant
>amounts of both bias and correlation,
I believe so, yes.
>so that the keystream that
>results is crypto-grade for realistic applications?
CRC only does what it does. I presume that "crypto-grade" values also
require unknowability and secrecy which of course places similar
demands on the input data.
But if we have physically-random input data with bias and some
limited-distance correlations, and if we can arrange to always put
enough data in so that for each hashing we put in substantially more
"entropy" than the amount of data we take out, the CRC should produce
practically unbiased and uncorrelated results.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: paper on all 15 AES candidates ??
Date: 2 Mar 1999 07:13:04 GMT
In <7bek8f$7ce$[EMAIL PROTECTED]> Fauzan Mirza <[EMAIL PROTECTED]> writes:
]Also, Twofish has an interesting property which will be described
]at the AES conference. The AES version of the paper can be downloaded
]from either Sean Murphy's or my home page.
]Fauzan
]==================================================================
] Fauzan Mirza Department of Mathematics
] Research Postgraduate Royal Holloway, University of London
]==================================================================
And then you do not give your home page address.
------------------------------
From: BORIS KAZAK <[EMAIL PROTECTED]>
Subject: Re: True Randomness - DOES NOT EXIST!!!
Date: 2 Mar 1999 06:47:01 GMT
Reply-To: [EMAIL PROTECTED]
R. Knauer wrote:
> (snip)
> And since the essence of the Universe is not existence, it must get
> its existence from a source different from itself. That source is the
> entity whose essence IS existence, called the Supreme Being.
> (snip)
> I do not hold the existence of the Supreme Being as a belief. I hold
> it as a rational principle.
>
> The existence of the Supreme Being is derived from the worldview of
> Realism. If you accept the objective reality of external objects, as
> Western scientists do, then the existence of the Supreme Being follows
> rationally.
> (snip)
> Bob Knauer
====================
And this is all very sad... If there indeed is some Supreme Being,
then IT is the Master, and we are merely slaves (or guinea pigs).
My philosophy as an atheist is very simple - I am a free man, there
is no Lord above me, no Supreme Being. I take guidance from no one,
and I am myself fully responsible for the consequences of my choices.
There is no word "believe" in my dictionary, I cannot "believe"
or "not believe". I must know, or I admit that I don't know.
And isn't it obvious that we see only certain kinds of processes
going on in the Universe not because other kinds of processes are
impossible, but simply because other kinds of processes go on
*without witnesses*, in such a universe organic life would be
impossible?
Respectfully BNK
------------------------------
Date: 2 Mar 1999 07:10:23 -0000
From: [EMAIL PROTECTED] (Sorcerer)
Subject: Re: One-Time-Pad program for Win85/98 or DOS
Crossposted-To: alt.security,alt.privacy
On Mon, 1 Mar 1999 22:31:11 -0800 "arcmight" <[EMAIL PROTECTED]> wrote:
>"... And now for the prosecution, the government will introduce evidence
>that the defendant, having used
>an insecure implementation of the one-time pad, which has been broken and
>reveals the true intent of the defendant,
>
>The cryptographic String:
>
>
>axka03in3nc9-085na;n/-0937ugh2wn3rtk.w9u23-9asfjW'NRF-0348u3425834250mnsdf/.
>n,zxcv84tasdfadsf
>
>Translates to:
>
> Bomb at midnite, death to all facists, burn the banks, loot and rape, long
>live the revolution
>
>
>For which under the Anti-Terrorism act of 1996 et al., we hereby request the
>death penalty...."
>
>
>< The unfortunate problem with one-time pads is that the government can have
>them say anything they want
>when they prosecute you, and how you gonna prove it's anything else?
The defendant doesn't have to prove anything. The prosecution must
prove that that's what the message says. Expert testimony to the judge
would be enough to exclude the government's interpretation - it has no
foundation.
The expert would testify (correctly) that it is equally probable that
the message really says "I love motherhood and apple pie".
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Musings on the PKZip stream-cipher
Date: Tue, 02 Mar 1999 06:56:06 GMT
On Mon, 01 Mar 1999 18:42:55 -0700, in
<[EMAIL PROTECTED]>, in sci.crypt Sundial Services
<[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>> >While my technical interest in this cipher is retired, I'd also like to
>> >stimulate any discussion I can on ways of analyzing and breaking such
>> >ciphers. I'd also like to know more about exactly why this cipher was
>> >constructed the way that it was.
>> >
>> >The core algorithm of the cipher is Update_Keys(char):
>> > Key(0) <- crc32(key(0),char)
>> > Key(1) <- Key(1) + (Key(0) & 000000ffH)
>> > Key(1) <- Key(1) * 134775813 + 1
>> > Key(2) <- crc32(key(2),key(1) >> 24)
>>
>> I have several times reported here that some years ago I was able to
>> resolve this part of the PKzip cipher. There is also an output step
>> not shown here which I did not resolve.
>
>I'm not quite sure what you mean here by the term "resolve."
We are confronted with 12 "key" bytes of unknown value. The goal is
to "resolve" those values.
>> The core is linear. Yes, it is a couple of different styles of
>> linear, which is basically the strength argument used in IDEA.
>> Nevertheless, I was able to reconstruct the 12 bytes of internal state
>> given exactly 12 bytes of known output (also the known input from
>> feedback, of course). In retrospect, this is what we expect from any
>> linear system. And once the state is resolved, we can run it forward
>> or backward as desired.
>
>Output? If this is true as stated, then the cipher is non-existent,
>since if you can reconstruct the state using only 12 known bytes of
>output you can by definition select any 12 bytes of ciphertext, compute
>the state it must be in, and run it backward to the start of the file,
>then forward to decipher the whole thing.
As I said, the cipher is more than the just the core. There is also a
nonlinear output step that I did not surmount.
But, yes, *if* the cipher were just the core, we would be talking
about an immediate practical break using only 12 known-plaintext bytes
(which we probably have from the structure of the compression).
But since nobody uses PKZIP as a cipher anymore, I'm not sure it
matters.
>> This was a long time ago, before the web, and before I was doing
>> somewhat formal articles. And without the last step, it is not really
>> a complete solution anyway. I'd have to get back into the work to
>> discuss details, and that seems unlikely now.
>
>Leaving us all with a tantalizing result somewhat akin to Fermat's Last
>Theorem.
I don't know what to tell you. I am not comfortable hand-waving this,
but you wanted "musings" and there they are. This was probably circa
91, 92, 93 or somewhere around there. I expect I gave
equally-tantalizing comments at the time, because it was *not* *a*
*break*.
As I recall I spent perhaps a couple of weeks on it over a longer
time, building on earlier work, then something came up that I had to
do and that was it. In those days I was programming original ciphers
under the delusion that someone would buy them because of their
quality. That was DOS. Nobody runs DOS anymore, but I am not
comfortable with myriad holes we must fill to make Windows secure.
>I conclude from this response that there is nothing published about your
>work on the web at this point, but was anything published on paper?
Again, it was not a break of the full cipher, and certainly not a full
theory, so it is not clear what basis there would be to publish. I
certainly at that time did not feel sufficiently in control of the
technology to publish it authoritatively. If the results are
sufficiently intriguing, I suppose somebody might fund me to explore
it further and publish for everybody to see. Or not.
>It
>sounds to me like there is some fundamental information about
>"linear-ness" and stream ciphers, which I could dimly discern by
>intuition, that must be formally expressed somewhere.
It long been known that linear ciphers are very weak. My work has led
me to believe that the ability to resolve internal state is an
inherent weakness of (presumably some forms of) linearness.
Note that here we have 3 different linear layers (CRC, LCG, CRC), they
are linear in different ways (mod 2, mod 2**32), and connected only by
one byte between each layer (and for input and output). Yet we need
only as much known-plaintext as the amount of hidden internal state to
define that internal state. As I recall I also tried single-bit
connections between layers, and more layers, with similar results.
The known values do not even have to be contiguous, but simply at
known positions in the stream. So we could instead use bit values, at
one bit per byte, but then of course would need 96.
>Terry, I'm hoping to start a fresh and interesting discussion thread
>here (how -long- can one talk about Enigma and random numbers? ;-) ;-)),
>and of course what is said here will become valuable public material by
>means of DejaNews. If you have the time to do so, I would be
>-extremely- appreciative if you could elaborate more clearly on what
>you've said here even if it requires a bit of digging into your past.
>And I'm quite sure there is (and/or will be) a silent appreciative
>audience out there with me.
Considering the "web bandwidth overage" fees that have started to kick
in on my web page, I'm not sure how much more appreciation I can
afford.
Currently I am trying to break away to "crash busy mode" to do some
diode noise analysis which I will publish if it is worthwhile. I will
admit that there are a many other important things to do, but any one
of us can do only so much.
Currently I am making my expert advice on the many subtle details of
physically-random RNG design available for a fee. That's what I do
now. When I eat, that's how I eat.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Anthony Naggs <[EMAIL PROTECTED]>
Subject: Re: Musings on the PKZip stream-cipher
Date: Tue, 2 Mar 1999 00:49:12 +0000
After much consideration Terry Ritter decided to share these wise words:
>
>>The core algorithm of the cipher is Update_Keys(char):
>> Key(0) <- crc32(key(0),char)
>> Key(1) <- Key(1) + (Key(0) & 000000ffH)
>> Key(1) <- Key(1) * 134775813 + 1
>> Key(2) <- crc32(key(2),key(1) >> 24)
>
>I have several times reported here that some years ago I was able to
>resolve this part of the PKzip cipher. There is also an output step
>not shown here which I did not resolve.
>
>The core is linear. Yes, it is a couple of different styles of
>linear, which is basically the strength argument used in IDEA.
>Nevertheless, I was able to reconstruct the 12 bytes of internal state
>given exactly 12 bytes of known output (also the known input from
>feedback, of course). In retrospect, this is what we expect from any
>linear system. And once the state is resolved, we can run it forward
>or backward as desired.
Which is pretty much what I told Paul Kocher, after I posted here about
the zip cipher, and I presume inspired his eventual paper. Someone had
promised to swing me some CPU time on a small supercomputer to attack
PKware's zip challenge, without which my interest fizzled out. (My 486
PC was rather slow for running my attack, and needed for other things
much of the time.)
>This was a long time ago, before the web, and before I was doing
>somewhat formal articles. And without the last step, it is not really
>a complete solution anyway. I'd have to get back into the work to
>discuss details, and that seems unlikely now.
The last transform is actually very easy to analyse:
unsigned char decrypt_byte()
local unsigned short temp
temp <- Key(2) | 2
decrypt_byte <- (temp * (temp ^ 1)) >> 8
end decrypt_byte
The core of this can be simplified to:
temp <- loword(Key(2) | 3)
mask <- (temp * (temp - 1)) >> 8
The 'mask' byte value is dependent on 14 bits of Key(2), (the most
significant 14 of the low word). A table can easily be constructed
listing 64 values of those bits for each value of the mask byte.
The mask byte in turn is trivially determined from a plaintext/
ciphertext byte pair.
Cheers,
Anthony
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Crossposted-To: talk.politics.crypto,comp.sys.intel
Subject: Re: Hardware Random Numbers: Not an *explicit* feature
Date: Tue, 02 Mar 1999 07:55:00 GMT
On Mon, 01 Mar 1999 21:17:56 -1000, in <[EMAIL PROTECTED]>, in
sci.crypt Somniac <[EMAIL PROTECTED]> wrote:
>[...]
>This is a thermometer designed by my friend David Hoff when he worked
>at Intel around 1986. It is an Intel patent under David's name. The
>diode reverse leakage current increases with temperature. A small diode
>and a large diode are sensed by a differential amplifier to detect
>when the large diode has an easily measurable current. At normal
>operating temperatures, diode currents are too small to be measured
>easily. No software is needed to use the thermometer. It is a hardware
>circuit that outputs a logic signal called "hot slash cold bar". This
>logic signal can cause an interrupt or other state.
HOT / NOT-COLD
I stand corrected about forward diode bias being necessary for temp
sensing.
Never mind....
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Define Randomness
Date: Tue, 02 Mar 1999 07:55:22 GMT
On Tue, 02 Mar 1999 00:14:28 -0500, in <[EMAIL PROTECTED]>,
in sci.crypt "Trevor Jackson, III" <[EMAIL PROTECTED]> wrote:
>[...]
>An issue worth addressing is the way to define insecurity for a cipher whose
>virtue is not based on work factor, but on undecidability. The classic vernam
>cipher does not have a work factor as far as I understand the term.
That sure sounds wrong to me. The work factor is the effort involved
in resolving the internal RNG state given known-plaintext.
>Yet it must
>admit degrees of insecurity.
Sure. There is different security in different RNG designs.
>For instance, if I use each key exactly twice. I
>have theoretically compromised my security.
Absolutely.
>But using each key exactly 1,000
>times would be a more serious weakness. Yet by your standards you would consider
>both systems insecure; the binariness imples they are *equally* insecure.
I would say that one cannot get more compromised than compromised. If
by "more serious" you imply that by good fortune The Opponent did not
pick up on the earlier error, you have just accepted what we demand a
cipher not do. We insist a cipher *prevent* giving The Opponent
access, no matter what courses he takes. The Opponents will not tell
us that they have failed to pick up an error -- so we must assume that
they used it. If it is sufficient to wish and hope The Opponent has
not spotted a weakness, we might as well wish and hope that The
Opponent is not looking at us at all, in which case why bother with
cryptography?
>>[...]
>> Sure, if somebody gets the key, they are in. But the issue in the
>> above paragraph was: "why not use an ordinary cipher to protect the
>> OTP key"? The answer is that we then depend upon the strength of the
>> ordinary cipher for security, which reduces the hoped-for security to
>> about that of the ordinary cipher. And that means we might as well
>> use the ordinary cipher -- which is far easier to use -- and forget
>> about the OTP.
>
>Only in the case of trivial application mechanisms (e.g., straight XOR). This is
>similar to the conclusion that PRNGs are useless for ciphers because a simple XOR
>is easily reversible, and once the key stream is visible it can be analyzed and
>then predicted.
>
>Non-trivial application mechanisms eliminate these straman arguments against
>PRNGs, and, I believe, against the Vernam system.
Surely you don't imagine that I have forgotten my own original work on
Dynamic Substitution combining which does just this? But when was the
last time you saw anyone (other than me) recommend using a serious
nonlinear combiner with state for an OTP? That could be a Latin
square, or Dynamic Substitution, or, presumably, something else. But
everybody insists that XOR is good enough for them because an OTP is
"proven absolutely secure." Right.
Nevertheless, for analytical purposes, it is worth assuming that The
Opponents have penetrated one level of strength so we can discuss what
strength means in the other level. We can just build an RNG and a
combiner and hope neither exposes the other, or we can try to see how
well each would stand on their own.
>[...]
>I suppose they are pretty tightly bound. Another property worth cataloging as an
>index is the portion of the cipher at which the analysts "inserts his wedge" as
>it were. There is a logical starting point for most attacks, often a particular
>operation that is vulnerable to analysis.
I think in most cases this is what the "information exposure" conveys.
Or were you thinking of something different? How about an example?
>[...]
>Yes. Exhaustive testing is rarely useful. We need a set of tests whose results
>can be extrapolated over larger regions than those tested. I believe a MITM
>style of testing may be possible. Given a cipher a theoretician might be able to
>define a representative set of tests whose results scale up to cover the entire
>system. I speak here not of the keyspace, but of round counts, S-box sizes,
>etc. Scalable ciphers will provide this capability. One we currently lack.
Allow me to just point out that *all* of my modern cipher designs are
scalable. I have yet to see a stampede to my technology.
>> And all this depends upon *having* a weakness test! In my opinion,
>> such a test must find *every* *possible* weakness, and must do so with
>> absolute perfection. I would be very, very dubious about trying to
>> estimate the "strength" of a cipher on the basis of a "strength" test
>> which could miss any number of innovative attacks.
>
>Try to avoid making test perfection into a grail.
There are two levels to experimental cipher analysis: 1) the ability
to find "weakness," and 2) the statistical sampling required to
achieve an expectation of the desired level of strength. Here (2) is
inherently imprecise; we understand it in a statistical context.
But (2) *depends* upon (1), and the only way (2) works, as far as I
can see, is the assumption that (1) is correct.
Again, a "weakness" test which only finds *some* weaknesses is not
sufficient to certify a cipher against arbitrary attack.
Of course if we can convince The Opponents to play fair and only use
the attacks we specify, then we don't need to consider other attacks.
Maybe there oughta be a law....
>I thought we had concluded
>above that perfect testing was not a useful concept. Consider that cryptology is
>a very new science (if it is a science; I tend to think not). There is great
>value in a compendium of all known attacks even if the collection is provably
>incomplete.
I think this is largely what we see in the literature and in various
crypto texts.
>The reason I find merit in this apparently inadequate tool is contained in the
>testing "correlation of forces". A weak cipher is probably going to fail many
>tests. A strong but flawed cipher may still fail multiple tests. A slightly
>imperfect (shall we use the gemologists scale: very very slightly imperfect?) may
>fail only one test.
I would still say that compromise is compromise. Even one fault is
sufficient to call the cipher broken academically, and to use another
cipher in practice.
Worse than that, we expect that most ciphers will fail no *tests* at
all. What they may fail is attack by Opponents, which we will not
know about, and it matters not how many attacks would have succeeded.
>A cipher that fails no test may still contain a flaw, but as the science matures
>it will become harder and harder for an adversary to detect the flaws that the
>assembly of tests fail to detect.
There is no way we can know this or assume that future attacks need be
harder. Those guys are smarter than we are, are better funded, and
have more experience, equipment, and time. They may have a shortcut.
An attack need not be harder at all if The Opponent has a break we
don't know about.
>In the limit we'll find that the analytic
>effort required to find a flaw may have such a high work factor that the cipher
>may have "security through subtlety".
There is no reason to assume that attacks we don't know about will be
more difficult than the attacks we do know about. In fact, every new
attack is easier than the one it replaces.
>Extrapolating from current, labor-intensive attacks may be like extrapolating New
>York City in 1900. The prediction was that by 1950 everyone in the world would
>have to be an NYC telephone operator, and the place would be covered by a layer
>of horse manure 50 feet thick. Automated testing would permit automated cipher
>mutation. Metaphorically, everyone in the world has to work for the NSA, and
>every message sent has 6.023e23 BCC recipients.
Current ciphers simply offer no confidence at all that only certain
attacks, certain classes of attacks, or only attacks of given minimum
effort will succeed. It is entirely plausible that new, innovative,
comparatively-simple attacks will be found for any cipher at some time
in the future. It is also plausible that The Opponents will have been
exploiting that attack almost from cipher introduction.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Lowball61)
Subject: Re: A New Public-Key Cryptosystem
Date: 2 Mar 1999 08:03:44 GMT
Thank all of you for your help.
However, please help me a little more.
In my example, M =
64
0D
9B
0D
82
8E
B8
B7
83
00
92
25
9D
00
25
In this array, 00, 25, and 0D are all repeated twice. How would one select
which of each pair was selected and summed to produce the total C5? For that
matter, how one one determine if a 00 row was selected at all? And how would
one determine that both 25 (or 0D) entries were not selected, since they would
sum to 00 (mod 2 : 25 XOR 25 = 0)?
How does reducing this problem to an affine transformation help to solve the
above?
In general, how does one solve the combination of a non-linear transform and a
linear transform, when the nature of the non-linear transform is hidden by the
combination?
It seems to me that one cannot solve non-linear problems with linear tools.
Perhaps there are ways to decipher the nature of the non-linear transform and
crack the code that way, but the question I ask first is: Can a non-linear
problem be solved by linear methods? Granted that the non-linear transformation
in the example is a very simple one, it still serves to ask the question.
Charles Larry Craig
------------------------------
** 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
******************************
