Cryptography-Digest Digest #347, Volume #9 Tue, 6 Apr 99 16:13:03 EDT
Contents:
Re: RC4 test (Jim Gillogly)
Real-time crypting ("Andrew I. Baznikin")
The Boomerang Attack (was: Re: FSE information anyone?) (John Savard)
Re: True Randomness & The Law Of Large Numbers (Darren New)
Re: True Randomness & The Law Of Large Numbers (Patrick Juola)
Re: True Randomness & The Law Of Large Numbers (Jim Felling)
Re: Announce - ScramDisk v2.02h (Dave Howe)
Re: True Randomness & The Law Of Large Numbers (Jim Felling)
Re: Encrypting Fields in Microsoft Access Database ("Brian A. Sayrs")
Re: DES-source ("Brian A. Sayrs")
----------------------------------------------------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: RC4 test
Date: Tue, 06 Apr 1999 09:13:06 -0700
[EMAIL PROTECTED] wrote:
> how long it takes to retrieve. The key is 40 bits long, so I couldn't imagine
> it taking long...
>
> The ciphertext is:
>
> 72 48 FC B6 76 FB 2C 10 13 2A 15 F8
>
> The plaintext is a text message, so you should be able to detect it.
The timing of a brute force attack on RC4-40 is pretty well known:
Damien Doligez cracked one in a week with a workstation farm, and
a cypherpunk consortium broke another in two or three days. An
RC5 challenge, also 40 bits, was broken by Ian Goldberg in 3.5
hours, also with workstations. The special-purpose DES machine
built by EFF (esp. John Gilmore and Paul Kocher) would knock off
a 40-bit DES key in seconds. Anybody who wants can crack their
own RC2-40 keys using the Counterpane screen saver.
For this particular challenge, 12 bytes is a bit sparse, even knowing
it's "a text message". Every 2^12 attempts you'd expect to get the
high bit off on all 12 bytes of plaintext, so that's 2^28 possible
plaintexts to eyeball or to score with tetragraphs, or whatever your
favorite plaintext recognizer is.
> I am willing to help (except giving the key...).
OK, how about some plaintext, to make up for that 2^28 space. Does
it end with a CRLF? How many spaces in it?
--
Jim Gillogly
Sterday, 15 Astron S.R. 1999, 16:03
12.19.6.1.10, 12 Oc 3 Uayeb, Third Lord of Night
------------------------------
From: "Andrew I. Baznikin" <[EMAIL PROTECTED]>
Subject: Real-time crypting
Date: Tue, 06 Apr 1999 18:59:29 +0700
If someone has the possibility to send me C/C++ sources of functions or
programs for real-time crypting or may be if you know any URLs please
send me it!
Thank you, Baznikin Andrew
<[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: The Boomerang Attack (was: Re: FSE information anyone?)
Date: Tue, 06 Apr 1999 16:38:36 GMT
Thirteen <[EMAIL PROTECTED]> wrote, in part:
>First on the agenda
>is a very impressive paper by David Wagner, a student at Berkeley,
>and a participant in sci.crypt. The Boomerang attack is a new
>form of differential cryptanalysis in which work is done on half
>of the rounds. The cipher is broken in half, like a meet in the
>middle attack. David showed a 3 dimensional diagram like a cube
>cut in half with the 4 top corners being 4 plaintexts and the 4
>bottom corners being 4 ciphertexts. 2 plaintexts are found with
>differential characteristics that have "the right differences".
>The resulting ciphertexts then are used to construct 2 more
>ciphertexts with "the right differences". Then decryption
>follows the reverse path through the cube into the middle,
>where conveniently, algebraic symbols are manipulated to cancel
>out some "stuff". The key is found by trying numerous keys to
>construct the cube that has the right differences. It takes
>much less work than an exhaustive search.
Having read the paper, I could draw a similar drawing...but I'm going to
skip trying to do it in ASCII graphics, I'm afraid.
The Boomerang attack does not double the *raw power* of differential
cryptanalysis. What it does do is increase its flexibility. If there is a
"kink" in one half of the key schedule to block one differential
characteristic from being useful, and a "kink" in the other half to block
another one, this attack lets you use two unrelated characteristics in each
half of the cipher to attack the whole cipher.
The paper refers to a "folk theorem", where a characteristic with
probability p is felt to be required, such that p^n, where n is the number
of rounds, is still significant above the noise level. The Boomerang
attack, though, still requires two characteristics, with probabilities p
and q, such that (p^(n/2))*(q^(n/2)) is significant - actually, n doesn't
have to be split in half, and the attack can be further generalized - and
this is why I say it hasn't actually vastly increased the *raw power*
involved.
How it works:
For the boomerang attack, a precise definition of what constitutes a
differential cryptanalysis "characteristic" is required. That definition
is:
Given a block cipher, or portion of a block cipher, having a
characteristic, this means that:
For a random input A, and a difference vector d, then for _every_ key k
which satisfies the condition about the key one wishes to learn is true or
not (i.e. every key with bit 3 equal to 1) E(k,A) xor E(k,A xor d) has -
for every one of its bits - a higher than 50% probability of being equal to
the characteristic, c, corresponding to d.
Thus, you can average out over different keys A, but you have one fixed key
k that you have to be able to learn something about.
Now, if one has two good - but unrelated - characteristics, each applicable
to one half of the cipher, one proceeds as follows:
Choose random inputs A. Let d1 be the difference vector for the
characteristic in the first half of the cipher.
A and A xor d1, when enciphered halfway, produce two middle values
differing by c1. When enciphered fully, though, they produce two results
with no particular relationship...call them B1 and B2.
Now, decipher B1 xor d2, where d2 is the difference vector for the second
half characteristic (going upwards), and do the same with B2 xor d2.
Halfway through the cipher, B1 xor d2, half deciphered, differs from B1
half deciphered (which is A half enciphered) by c2.
Similarly, halfway through, B2 xor d2 differs from B2 half deciphered
(which is A xor d1 half enciphered) by c2.
Since A and A xor d1, half enciphered, differ by c1, then the two
quantities above - each equivalent to one of those quantities, but XORed
with c2 - also differ by c1.
Hence, B1 xor d2 fully deciphered differs from B2 xor d2 fully deciphered
by d1. Provided, that is, the key k has the one (or two) attributes for
which the characteristic tests. And, of course, only with a certain
probability, which means lots of A values need to be tried.
John Savard (teneerf is spelled backwards)
http://members.xoom.com/quadibloc/index.html
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Tue, 06 Apr 1999 16:55:05 GMT
R. Knauer wrote:
> I define true randomness in two ways, one by the TRNG specification
> and the other by the output of a quantum computer programmed to
> calculate true random numbers.
How about a classical computer programmed to simulate a quantum computer
programmed to calculate true random numbers? Would that be true
randomness? Can you justify your answer?
--
Darren New / Senior Software Architect / MessageMedia, Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"Practical Necromancy: Chapter One - Proper Use of Shovels"
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: 6 Apr 1999 12:12:53 -0500
In article <[EMAIL PROTECTED]>, sb5309 <[EMAIL PROTECTED]> wrote:
>I have wanted to say something Jerry just mentioned below; I resisted the
>the urge because I am a complete novice in what is going on, but I did think
>about randomness.
>
>It is just like what Jerry said :
>
>Assuming we produce 100 bits of 0's and 1's. There are thus 2^100
>arrangements. Let r be the no. of random arragements, and n be the no. of
>non-random arragements. Thus
>
> 2^100 = r + n
What the hell does a "non-random" arrangment mean?
When you're talking about a "random arrangement" in this context, you
have to be very careful to distinguish
* an arrangement produced by a "random" process
and
* an arrangement with no evident order (apparently "random")
The two are *NOT* synonymous.
Your counting argument doesn't go through -- there are literally an
infinite number of possible processes, some (many) of which produce
the same outcome but by different paths. Just because something has
no evident order does not mean that it was produced by a random
process, nor does the fact that something is a random process mean
that none of its outcomes will appear ordered.
Patrick
------------------------------
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Tue, 06 Apr 1999 13:55:00 -0500
Herman Rubin wrote:
> In article <[EMAIL PROTECTED]>,
> Jim Felling <[EMAIL PROTECTED]> wrote:
>
> >"R. Knauer" wrote:
>
> >> On Thu, 01 Apr 1999 09:58:42 -0600, Jim Felling
> >> <[EMAIL PROTECTED]> wrote:
>
> ..............
>
> >Either I have a 1)defective TRNG that just fooled me on my examination or
> >2) a working TRNG that generated statistically unlikely output.
>
> >Given those are the only 2 possible hypothesis Occams razor would make me choose
> >hypothesis 1 and I therefore would kick out.
>
> There are an infinite number of hypotheses; the hypothesis that you
> have a TRNG is one which is essentially impossible. Occam's razor
> is very definitely misused.
Accepted .
But replace TRNG with RNG above and I will stand behind those words.
>
> --
> This address is for information only. I do not claim that these views
> are those of the Statistics Department or of Purdue University.
> Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
> [EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
From: DHowe@hawkswing (Dave Howe)
Crossposted-To: alt.security.pgp
Subject: Re: Announce - ScramDisk v2.02h
Date: Tue, 06 Apr 1999 19:27:52 GMT
Reply-To: DHowe@get_email_from_sig
In our last episode (<alt.security.pgp>[Fri, 02 Apr 1999 14:51:15
GMT]), [EMAIL PROTECTED] (aman) said :
>We have no competitors.
You have - you just don't know it - they sell their product, so regard
a FREE product better than the one they sell as a threat
... maybe I should crosspost this to alt.consipiracy.software.american
:+)
>Scramdisk is not a commercial product, and we don't care if people use
>it or not. It is up to them to make their own mind up.
And most of us are unspeakably greatful (even if it would be easier to
get our employers to use it if it was payware, paradoxically enough
:+)
>To be honest, I sometimes wonder why I bothered.....
My best guess would be :-
1) Got frustrated at the software that couldn't do what Scramdisk can
2) Went out and wrote something to fix it
3) Decided that, given it was already written, it wouldn't hurt to
give it to everyone
4) Found out that people occasionally look suspiciously at free gifts
as good as this one....
Anyone want to append to this list? :+)
--== Dave ( is at) hawkswing.demon.coDOTuk ==--
And the quote for today is... "OhYeah!...Incoming!!"
------------------------------
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Tue, 06 Apr 1999 14:52:23 -0500
"Bryan G. Olson; CMSC (G)" wrote:
> R. Knauer ([EMAIL PROTECTED]) wrote:
> : On Thu, 01 Apr 1999 22:38:43 GMT, [EMAIL PROTECTED] wrote:
>
> : >Feller's point in no way implies that a large portion of molecules
> : >will be farther than 10,000 units from the mean after a million
> : >unbiased leftward/rightward events.
>
> : >In fact 10,000 units at n=1000000 is 20 standard deviations; 0.05*n
> : >is 100 standard deviations. Even with a gallon of perfume, we expect
> : >_no_ particles that far out.
>
> : Then how do you explain the weird "abnormal" things that Feller
> : discusses in the chapters on the random walk and the uniform Bernoullu
> : process? And what is his second volume about fluctuations all about?
>
> : Is he advancing snake oil, or is there something fundamental about
> : random processes he is trying to tell us?
Neither. There are huge quantities of possible points out near the extremes.(
|Sn(X)| >10000) I am betting there are at least 2^10000 + such points.
However in the overall space 2^10000 is a drop in the bucket.
for Smaller N things get much less definite.
N=25 SD=2.5 Most of the values are not within 0.5N of the mean
N=100 SD =5 30%+ of the values differ by .05N from the mean
N=400 SD=10 10% of the values differ by .05N from the mean
N=900 SD=15 less than 1% of the values differ by such.
So for small runs weird stuff will be common -- the larger the run the more
likely that the overall likelyness of any weird stuff drops-- this is due to
the fact that the number of "well behaved" sequences increases much more
rapidly than the number of "badly behaved" sequences.
>
>
> I haven't written anything that implies no statistician will write
> about abnormal phenomena or fluctuations. You simply have not
> understood what theory applies where.
>
> : Quantum mechanics is all about true randomness, yet after nearly a
> : full century, no one has come up with a satisfactory mathematical
> : model to explain the "collapse of the wave vector".
>From a pure physical viewpoint do we need to? -- all we need is a system that
gives us useful predictions -- just because a theory doesn't have all the
answers does not mean that that theory is not worthwhile for anything
practical.
>
>
> And to show that your predictions about a random walk are wrong,
> we certainly don't need to.
>
> : IOW, I am challenging your contention that true randomness can even be
> : modeled mathematically, even to the extent that you can determine with
> : reasonable certainty tbat a process is not truly random based on
> : statistical tests.
>
> But your doing it by not defining your terms.
>
> : I find it a bit curious that no one has challenged my contention that
> : if you could model true randomness using statistical models, that you
> : could then use them to filter the output of PRNGs to produce true
> : random sequences - which we know is impossible.
>
> O.K.; I'll bite. First I challenge you to define what you mean.
> I'll assert that statistical hypothesis testing can show that some
> bad candidate TRNGs are in fact bad. Now precisely how can you use
> this to deterministically generate true random numbers?
>
> : I have read most of what Greg Chaitin has written about the Unknown in
> : mathematics, and I am basing much of what I am claiming on those
> : meta-mathematical considerations - although it does not show in these
> : discussions. I am waiting to get past these hurdling blocks, so we can
> : really get down to business with regards to True Randomness.
>
> While I've merely read about the fundamentals of probability and
> statistics. I've found that understanding a little is better than
> cataloging a lot. I've often joked that I have a friend who's into
> Chaos Theory, only he thinks the point is that we must find and kill
> some butterfly.
>
> : >You wrote
>
> : Sorry, but I do not care to spend time on nitpicking.
>
> Gee, I was under the impression you lived for it.
>
> : >> Are you saying that a run of 100 zeros conclusively demonstrates that
> : >> a TRNG is malfunctioning? How about a run of 100 zeros in a sequence
> : >> of 10^9 bits?
>
> : >Yes. Reject the candidate TRNG.
>
> : No. The best you can decide is that the TRNG is *possibly* broken,
> : which then requires you to check it out.
>
> Given any reasonable estimate on the probability that the TRNG
> is broken in such a way as to produce 80 zeros in a row, I
> quantify a lower bound on the probability that the candidate
> TRNG is broken, and that probability will be close enough to one
> that I can safely reject it.
>
> Even with no estimate on the probability of broken TRNGs, I
> can say that my policy of rejecting TRNGs if the 10^9 bit test
> produces a string of 80 zeros has a negligible probability of
> rejecting a good TRNG. If I, and everyone else in the world,
> devote the rest of our lives to TRNG testing, we would not
> expect anyone adopting this criterion to reject a single good
> TRNG.
>
> : >Yes, but let's solve one problem at a time. You want precise
> : >quantitative arguments, I ask at least that you follow those
> : >given. Under our binomial distribution with p=q=0.5 and
> : >n=1000000, the number 0.05*n is 100 standard deviations. We
> : >do not expect particles outside of 100, or even 20 standard
> : >deviations from the mean.
>
> : Yet Feller shows that a significant number of sequences are outside
> : that range. It all depends on how you pose the measurement.
>
> It was you who posed the question, and you said it was a
> binomial distribution. Now can you quote Feller as saying
> a significant proportion of sequences with p=q=0.5 and n=
> 1,000,000 will differ from the mean by 50,000 or more?
>
> : I have known for over 35 years that the Gaussian distribution falls
> : off very slowly. And I realize that the lone sequence at the far outer
> : reaches is the sequence that is all zeros or all ones, and that
> : compared to the rest of the sequences, it is very lonely out there.
The speed with which it falls off is related to how large a sample you have.
>
>
> Again, I must point out the importance of quantitative reasoning.
> How long you've known what and the loneliness out there will not
> help us answer the question. One hundred standard deviations
> will.
>
> : What does that have to do with true randomness, in particular
> : statisticall measures of true randomness?
>
> It was you who brought the question up, so you can decide what
> it has to do with what you were talking about. I cannot see
> how it could have been relevant if your conclusions were correct,
> but irrelevant that your conclusions are wrong.
>
> --Bryan
------------------------------
From: "Brian A. Sayrs" <[EMAIL PROTECTED]>
Subject: Re: Encrypting Fields in Microsoft Access Database
Date: Mon, 5 Apr 1999 17:51:40 -0700
All of VB's internal workings are Unicode...sorry you lose 16 bits/bit :)
Using VB for bitbashing is like using a foam rubber hammer to drive a nail.
And I say this while being a big fan of VB...but C has it's place and this
is it.
B
[EMAIL PROTECTED] wrote in message <7eba8k$c8$[EMAIL PROTECTED]>...
>>wtshaw wrote in message ...
>>>In article <7e3kms$svl$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>>>
>>>> If you want to do encryption, you will need to use C. VB lacks powerful
>>>> bit-bashing operators (AFAIK it doesn't have bit shifting) and forces
>>>> you to use signed operators.
>>>>
>>>BASIC has very powerful string functions. Rotations are no problem
either,
>>>merely concatenate a string with itself and use MID$ to select the
>>>starting point and original length in the doubled string. This works
>>>well, use it all the time.
>>
>>Am I missing something?
>>Bit ops and string ops are not the same thing at all.
>>
>
>Unless you feel like wasting 8 bits (or more? does VB force unicode?) to
>express 1 bit ... '111011' ... excuse me while I go puke ...
>
------------------------------
From: "Brian A. Sayrs" <[EMAIL PROTECTED]>
Subject: Re: DES-source
Date: Mon, 5 Apr 1999 17:37:01 -0700
"Applied Cryptography," Second Edition, by Bruce Schneier
(John Wiley & Sons, 1996) About $50 US.
Pontus wrote in message <[EMAIL PROTECTED]>...
>Anyone here that can point me to some source to some DES-enrytption...
------------------------------
** 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
******************************
