Cryptography-Digest Digest #872, Volume #8 Sat, 9 Jan 99 16:13:04 EST
Contents:
Re: RSA-Modulus decomposition (David Hamilton)
Re: DES? (Matt Curtin)
Re: Cubes Inside Squares (John Savard)
Re: U.S. Spying On Friend And Foe (Withheld)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: Practical True Random Number Generator (R. Knauer)
Re: Birthday Attack calculations. ("Trevor Jackson, III")
Re: On the Generation of Pseudo-OTP ("Trevor Jackson, III")
Re: On the Generation of Pseudo-OTP ("Trevor Jackson, III")
Re: On the Generation of Pseudo-OTP ("Trevor Jackson, III")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Hamilton)
Crossposted-To:
alt.privacy,alt.security,alt.security.pgp,comp.security.pgp.discuss,talk.politics.crypto
Subject: Re: RSA-Modulus decomposition
Date: Sat, 09 Jan 1999 17:30:43 GMT
=====BEGIN PGP SIGNED MESSAGE=====
[EMAIL PROTECTED] wrote:
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (David Hamilton) wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> [EMAIL PROTECTED] wrote:
>> >Hello all,
>> >It is very easy to find decomposition of a
>> >modulus to it�s primes.
>> >Let n=pq be a modulus. Let m be a least
>> >message for which m^2 mod n = m.
>> >Then m-1 is p or q.
>> (snip some)
>> This is how things are. Alex ([EMAIL PROTECTED]) makes silly,
>> untrue
>> claims. People issue challenges that give him/her a chance to prove those
>> claims. Alex refuses to accept all challenges. Why? Because Alex makes
>> silly,
>> untrue claims.
> So far he rufuses to play the games according to Your RULES which
>are far from helpful.
Alex ([EMAIL PROTECTED]) makes claims. A number of people challenge
him/her to prove those claims. Alex refuses .... because he/she is making
silly, untrue claims. It will surprise nobody that David A. Scott who also
makes silly, untrue claims should be sympathetic to such an approach. Just
one of David A. Scott's silly claims is that he would break IDEA .... during
1997. More silly, untrue claims can be provided on request.
(snip some)
>David Scott
>P.S. I also refuse to play Hamilton's games it is fun to see
>him rant and rage. But I hope you can show with code I can
>coimpile and understand. Don't worry people like Hamilton
>could never follow youe code anyway.
As always, a desperate attempt to divert people's attention away from the
fact that there is never any evidence and never any answers. There is only
ever evasion. I bet that David A. Scott and Alex will get on tremendously
well together in never (any evidence and) never (any answers) land.
David Hamilton. Only I give the right to read what I write and PGP allows me
to make that choice. Use PGP now.
I have revoked 2048 bit RSA key ID 0x40F703B9. Please do not use. Do use:-
2048bit rsa ID=0xFA412179 Fp=08DE A9CB D8D8 B282 FA14 58F6 69CE D32D
4096bit dh ID=0xA07AEA5E Fp=28BA 9E4C CA47 09C3 7B8A CE14 36F3 3560 A07A EA5E
Both keys dated 1998/04/08 with sole UserID=<[EMAIL PROTECTED]>
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com>
Comment: Signed with RSA 2048 bit key
iQEVAwUBNpeNKso1RmX6QSF5AQHsfgf+JHiOAsZ6Fn4r7bDkiNXa64+bYxC0c/59
yvkskQzD+cIWjCzD1JYrNgDNkYUKuZX4fxcNY6LR3ao6BVTHeeEfS/puJ8qwIEJr
SYibOJs8dU0ujYnUwRuiTu+lpEjY2vbyhNzc+c1Pju38GzqdN8eJF08YhyQoo1MY
oHcdwgFUh7nHw2JxiIuvCfdds0dQoSSjbeZ69zjUo3vJGWoQL5ss/37+sEFXCnsh
LPNq5t2ZuXb0TL3lFzi6KDnc6MY3ji7jcewRA/QCMlkhOkyBUZuxMuhMLfgLsovQ
laXtcvBa+nfj9f5L3Xw2sfQaClUr7bdEXxPpDHvxOaPtyJSwG0a6bw==
=0ZtL
=====END PGP SIGNATURE=====
------------------------------
From: Matt Curtin <[EMAIL PROTECTED]>
Crossposted-To: alt.security
Subject: Re: DES?
Date: 09 Jan 1999 14:29:07 -0500
"TERACytE" <[EMAIL PROTECTED]> writes:
> Does anyone know where I can find information on the DES algorithm's
> weaknesses?
The algorithm itself has stood up to many years of exhaustive
analysis. However, there are some weak keys for DES, and the key size
is too small for it to be suitable for much in the way of serious
protection.
Schneier's "Applied Cryptography", 2nd ed has a discussion of DES and
pointers to much more information. Note that since that time three
different groups have broken a DES key by brute force:
o DESCHALL, led by Rocke Verser,
http://www.frii.com/~rcv/deschall.htm
o distributed.net Project Monarch
http://distributed.net/des/
o EFF's "Deep Crack"
http://www.eff.org/pub/Privacy/Crypto_misc/DESCracker/HTML/19980716_eff_descracker_pressrel.html
http://www.cryptography.com/des/
> (How I have the right newsgroup. My appologies if I don't.)
news:sci.scrypt would be better
--
Matt Curtin [EMAIL PROTECTED] http://www.interhack.net/people/cmcurtin/
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Cubes Inside Squares
Date: Sat, 09 Jan 1999 19:43:47 GMT
[EMAIL PROTECTED] () wrote, in part:
>This example, fortunately, involved an even number of digits. Also, not
>only did the unenciphered symbol, *, not appear, but there were also no
>symbols using the + - symbol set: these, being uncommon, may not encipher
>well.
In considering a couple of alternatives, I think the best way to deal
with that is not to use the + - symbol set; omit that small cube, and
the * symbol, and use instead one extra 3x3 square.
The 3x3 square can stand for pairs of two symbols from the ABC
alphabet.
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
From: Withheld <[EMAIL PROTECTED]>
Subject: Re: U.S. Spying On Friend And Foe
Date: Sat, 9 Jan 1999 20:00:49 +0000
Reply-To: Withheld <[EMAIL PROTECTED]>
In article <[EMAIL PROTECTED]>, Jim Dunnett
<[EMAIL PROTECTED]> writes
>On Wed, 6 Jan 1999 22:52:57 +0000, Withheld <[EMAIL PROTECTED]>
>wrote:
[cut]
>
>I fail to see how the OSA makes someone keep secrets!
>
>There have been as many Brit defectors as American.
>
Please note, my original comments were that Mr Kim Philby made his
reputation due to compliance with the Official Secrets Act. If you wish
to quote me please do so accurately.
--
Withheld
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Sat, 09 Jan 1999 20:03:32 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 9 Jan 1999 17:51:36 +0000, [EMAIL PROTECTED] (Paul L.
Allen) wrote:
>> We discussed this exact thing at length a year ago and concluded that
>> what you say is theoretically correct, namely that 000...0 is a valid
>> output, but it is so unlikely for any practical length sequence that
>> it must be taken as a sign of malfunction.
>*Any* pattern of output you specify is equally unlikely. All zeroes
>is as likely, or unlikely as all ones, 123451234512345, 314159265359,
>2718281828,... Well, they're all equally likely a priori. A posteriori
>is another matter - whatever turned up, turned up.
That is correct.
The significance of a sequence with all 0s or all 1s is that it is
indicative of common electronic problems like a shorted or open output
and serves as prima facie evidence of a likely malfunction.
>Even ignoring the strange English, I don't know what you're getting at.
You will have to read Chaitin's papers to see what I am getting at.
Chaitin probes the fundamentals of number theory and asks what are the
limits of decideablilty. He is following in the footsteps of Godel and
Turing. If you want to be well-versed in the topic of randomness,
Chaitin is a must read.
http://www.umcs.maine.edu/~chaitin/
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/
>There is nothing I know of in probability theory that says you cannot
>toss an unbiased coin 100 times in a row and get 100 heads. Not only that,
>getting 100 heads is neither more nor less likely than any other sequence
>of heads and tails you care to name.
That is correct. What is your point?
>> Therefore if a TRNG starts outputting unlikely sequences like 000...0
>> or 111...1, for any decent length N, that means it is broken, even
>> though such sequences are theoretically possible.
>I'd *suspect* it was broken. I'd check the circuitry. I'd see what
>another model produced. But, unlike you, I would not conclude that
>a TRNG outputting all zeroes *must* be broken.
I think we are saying the same thing. When I say "must" I mean
"extremely likely", not "necessarily". Your use of the term "suspect"
is a bit too weak for me, although it is technically correct.
> When you say "unlikely
>sequences like 000...0" you are making a fundamental error. That sequence
>is no more or less likely than any other sequence you could name of the
>same length.
I do not believe I meant to imply anything like that. My use of the
term "unlikely" is consistent with the meaning I intended -
vanishingly small probability of occurance. A sequence of 1 million 0s
has a "vanishingly small" probability of occurance, even though it is
equiprobable with all other 1 million bit sequences.
I suspect you are being a little overbearing in your enforcement of
the strict meanings of terms. This is not a refereed journal we post
to - most people know exactly what is meant by "unlikely" in the
context of the discussions here. In fact, that terms was used widely
by real cryptanalysts in our discussions a year ago on this topic.
>> But when we discussed the prospect of testing for other "non-random"
>> sequences, for example ones with abnormal bias, posters here said that
>> it is not correct to filter such sequences or you will begin to leak
>> information.
>That's the point. Every so often, a TRNG will produce the run "0", less
>often it will produce the run "00", less often than that, it will produce
>the run "000", etc. If you eliminated runs of n zeroes (for whatever value
>of n you think indicates brokenness) you would be biassing the output of
>the TRNG.
If the run of all 0s of any practical length were eliminated it would
not bias the TRNG in any pracitcal way. However, if you start trying
to eliminate other biases, then you will most definitely mess up the
TRNG.
The significance of all 0s or all 1s has to do with the fact that they
are signals of electronic problems and "must" not be ignored.
>> You should ask how much information is leaked by interpreting that a
>> sequence of all 0s or all 1's means a broken TRNG. I believe the
>> answer is that no information is leaked - that is, by stopping the
>> TRNG and perhaps fixing it, you do not compromise the total
>> unbreakability of your OTP system. IOW, being safe doesn't cost you
>> anything in terms of security.
>See above. You're decreasing the randomness from 1 bit of randomness
>per bit of data to something less. How much less depends on how many
>zeroes you have to see in succession before you filter them out, and what
>other sequences you filter out for similar reasons.
See above. The only sequences we are proposing to filter are those
with all 0s and all 1s. That is not going to impact the security of
the TRNG for realistic sequence lengths. And, as mentioned several
times in this discussion, you cannot filter any other biased sequences
or you WILL mess up the TRNG.
I think we are in complete agreement on all issues here if you will
concede that runs of all 0s and all 1s signal a likely broken TRNG if
the sequence is of practical length - say 10,000 bits, which is not
that many to buffer while a skew test is being performed.
Bob Knauer
"We hold that each man is the best judge of his own interest."
--John Adams
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Sat, 09 Jan 1999 20:09:16 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 09 Jan 1999 10:51:14 -0500, "Trevor Jackson,III"
<[EMAIL PROTECTED]> wrote:
>> I disagree. A TRNG can be made to crypto-grade specifications in that
>> it would take more energy than exists in the Universe to break the
>> OTP.
>I disagree.
You left out the context in which I made that statement.
Perhaps I should have worded it so that leaving out the context would
not have made the statement seem incorrect. But that gets tiring to do
all the time.
>The reason OTPs are valuable is that one cannot "break" them
>when used properly.
I know that. What is your point?
Bob Knauer
"We hold that each man is the best judge of his own interest."
--John Adams
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Practical True Random Number Generator
Date: Sat, 09 Jan 1999 20:15:36 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 09 Jan 1999 09:03:44 -0800, Anthony Stephen Szopa
<[EMAIL PROTECTED]> wrote:
>Practical True Random Number Generator
>
>I think I have just come up with a practical device to generate true
>random numbers.
Why go to all that trouble when you could sample the noise from an
open input on 20 buck sound card?
Also, keep in mind that any electronics is very susceptible to ambient
electromagnetic pickup such as 50-60 Hz line current.
The best TRNGs are digital in nature, like radioactive decay, where
bias can be removed by taking combinations of measurements such as
timing intervals in opposite directions of time, and where there is
very low susceptibility of the measurement results to ambient signals.
Bob Knauer
"We hold that each man is the best judge of his own interest."
--John Adams
------------------------------
Date: Sat, 09 Jan 1999 15:20:47 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Birthday Attack calculations.
> The whole point of testing on small hashes and extrapolating is that
> is computationally impossible to do a birthday attack on a large hash.
> For a 256 bit hash you will need to create more than 2^128 hashes
> before the odds of a collision reach 50%.
>
> Fred Van Andel
Something is wrong with this paragraph. Either the attack is not a birthday
attack, or the odds of a collision are much higher. An exhaustive search of
a 2^256 element state space has a 50% chance of a match agains the target of
the search. This is not a birthday attack.
A birthday attack searches for any matching pair rather than a match against
a target. Thus a birthday attack searching N states implies generating O(N)
states, but comparisons among N states means O(N^2) comparisons (assuming
the states are not generated in an order that allows comparison against
neighbors only). Thus for N small the generation cost may dominate the
overall cost of the search but for even a 40 bit key the comparison cost
will dominate due to the 2^79 comparisons required.
The odds of finding a matching pair among N of M states is the product over
0 to N-1 of the expression (M-i)/M.
odds = 1;
for i=0 to N-1
odds = odds * (M-i)/M
Thus a birthday attack can find a matching pair of elements much faster than
an exhaustive attack can find a match for a chosen target.
------------------------------
Date: Sat, 09 Jan 1999 15:29:45 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
R. Knauer wrote:
> On Sat, 09 Jan 1999 09:44:07 -0500, "Trevor Jackson,III"
> <[EMAIL PROTECTED]> wrote:
>
> >If the first 50 bits from the device are all ones do we have a biased
> >device or an N-sigma event? I believe this question to be undecidable
> >without further samples from the device.
>
> But it does you no harm to treat such an occurance as prima facie
> evicence that your TRNG is malfunctioning, since the likelihood of
> such an occurance is extremely small.
>
> IOW, by treating such a sequence as a warning that your TRNG *might*
> be broken, you leak no information in your OTP ciphers. Just stop the
> TRNG, inspect it for damage, fix it if necessary and begin again.
>
> A perfect example would be unplugging the lava lamp on the SGI
> Lavarand TRNG. (http://lavarand.sgi.com/)
>
> Bob Knauer
Well, let's see. 2^50 is about a quadrillion. Not much by crypto
standards. Why I encounter such an event roughly every 100 (galactic)
years!
;-)
------------------------------
Date: Sat, 09 Jan 1999 16:01:04 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
R. Knauer wrote:
> On Fri, 08 Jan 1999 09:21:36 +0100, Mok-Kong Shen
> <[EMAIL PROTECTED]> wrote:
>
> >Please note that in NO place in my original post there were a claim
> >of the sort 'Hi, look, I have invented something exactly as good
> >as an ideal OTP!'.
>
> I realize that. But I am pointing out that by using the term "pseudo
> OTP", you are implying that it is a good approximation to an actual
> OTP.
So use the RNG convention. POTP for the fake and TOTP for the real
thing. We acept the fact that there are good PRNGs and bad PRNGs.
Similarly we should expect there to be more or less good POTPs. It's a
terminology issue not a fundamental issue.
> There is a *fundamental* difference between a natural language text
> stream - however you doctor it - and the output of a TRNG.
No. From the first principles of information theory, information --
entropy -- is identical to unpredictability. A really good TRNG has 1 bit
of entropy per bit of data. But that is based on very careful sampling of
the physical process. Even quantum events indicate correlations. Some of
which appear to violate the speed of light rule.
Now text also has entropy. Raw text has less than one bit of entroy per
bit of data, but there is entropy -- unpredictability -- available in the
text. If you choose a poor sampling mechanism or over-sample the data
you'll get less entropy per bit than the desired 1:1. But there is no
question that entropy is available.
Thus, at the fundamental level there is no difference. Any differences
are part of the respective sampling methods not the source of the entropy.
> >I was simply calling attention to a (I believe)
> >possibly fruitful way of obtaining something (I term it pseudo-OTP)
>
> And it is that usage to which I object, not on pedantic grounds but
> because it is fundamentally incorrect usage.
Please amplify the natore of the error in light of the comments above re
terminology and fundamentals.
> >that could, on the assumption that suitable techniques (either
> >currently known as I sketched or yet to be developed or refined)
> >are applied,
>
> We already discussed/debated that whole matter a year ago and
> concluded that a text cipher, no matter how you buggered it, is still
> fundamentally different from an OTP generated by a TRNG.
Wrong,
> >approximate an ideal OTP
>
> One cannot "approximate" an OTP per se. One can approximate the
> unbreakability, perhaps.
>
> I think what you are trying to say is that it may be possible to
> concoct a text stream cipher that is, to a very good degree of
> approximation, as good as an OTP.
>
> >to some (for practical
> >purposes) satisfactory degree just as some good hardware devices
> >are supposedly already doing that way.
>
> That remains to be proven. The discussion a year ago raised serious
> doubts with respect to text streams. The problem was how to remove the
> inherent correlations in the least significant bits selected for the
> bit sequence. I proposed using the decorrelation methods described by
> Schneier in his main book, but others claimed that such methods did
> not remove text stream correlations, even if the stream were
> antiskewed first.
If this conclusion is correct then we have an important addition to the
science of information theory. What are the units by which we measure the
amount of magical correlation in a text stream? Do newpaper text, poetry,
source code, and TV scripts all share the same degree of this special
correlation?
This stuff that is inseperable from text reminds me of the magical fluid
that was part of all matter and that created heat when rubbed
(philosgin?). Does it have any other special properties?
> >I hope that this clears
> >up some misunderstandings. I don't doubt that much experiments
> >are needed in order to get really good pseudo-OTP.
>
> I still object to the use of the term "pseudo-OTP" as being
> fundamentally incorrect.
>
> Look, I used the same term a year ago and got my stuff jumped from all
> quarters. And I ended up agreeing with those critics because the point
> they were making had very fundamental significance.
>
> The fact that it took some thousand to get it right is a measure of
> how confusing this topic can be, largely due to prejudices that come
> from learning statistical mathematics.
>
------------------------------
Date: Sat, 09 Jan 1999 16:09:42 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
R. Knauer wrote:
> >But note that there are also auto-correlations. In general, akin to
> >the texts, many sources can be used, for instance digitalized pictures,
> >photos, etc.
>
> Then that means that you have to come up with a crypto-grade technique
> to remove such correlations, and prove that it works as advertised. I
> tried that once, citing a published technique, and it got shot down by
> the cryptographers on here.
Is it your position that it is impossible to come up with such a correlation
removal technique? or that it is hard to do so and none is now known?
------------------------------
** 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
******************************
