Cryptography-Digest Digest #105, Volume #13 Sun, 5 Nov 00 21:13:01 EST
Contents:
Re: Brute force against DES ("John A. Malley")
Re: BENNY AND THE MTB? (Bryan Olson)
Re: Brute force against DES (David Wagner)
Re: ECC choice of field and basis (Anwar Hasan)
Re: Microsoft's script encoder (Darren New)
Re: Brute force against DES (Sundial Services)
Re: Microsoft's script encoder (Sundial Services)
Re: BENNY AND THE MTB? (Tim Tyler)
Re: BENNY AND THE MTB? (Tim Tyler)
Re: Crypto Export Restrictions (Scott Craver)
Re: Crypto Export Restrictions (Scott Craver)
Re: Rijndael 128/192/256 implemented in GPG 1.0.4 (Tom St Denis)
XOR Software Utility (freeware) available from Ciphile Software (Anthony Stephen
Szopa)
Re: BENNY AND THE MTB? ("Matt Timmermans")
Re: Birthday messages ("Douglas A. Gwyn")
Re: hardware RNG's (Guy Macon)
----------------------------------------------------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Brute force against DES
Date: Sun, 05 Nov 2000 13:11:42 -0800
Francois Grieu wrote:
>
> "John A. Malley" <[EMAIL PROTECTED]> wrote :
>
> > Given plaintext and corresponding ciphertext, and (assuming) the
> > ciphertext is in ECB form (no chaining), consider using redundancy
> > in the plaintext (if present) to speed up the search for the
> > correct key.
>
> I do not get it at all. Assuming one gets a known plain-ciphertext
> pair, all there is to do is find a key (probably there is
> only one) that maps the two. Redundancy of the plaintext is
> perfectly useless.
The mistake in explanation is mine. What I should have said is:
The less redundant the plaintext, the faster the comparison between
known plaintext and candidate plaintext resulting from trial decryption
of the ciphertext with a candidate key.
If the plaintext block of eight, 8-bit bytes consists of 8 different
values - b1, b2, b3, b4, b5, b6, b7, b8 - then when checking the
candidate plaintext resulting from trial decryption with candidate key K
- d1, d2, d3, d4, d5, d6, d7, d8 - check first that b1 == d1. If not,
throw away this key. There is no need to check the remainder of the
decrypted output against the remainder of the known plaintext. This
reduces the time spent verifying a key.
If b1 == d1 then check if b2 == d2. If not, stop and throw the key away.
If the plaintext contains several identical byte values and several
unique byte values - b1, b2, b3, b4, b5, b4, b4, b5 - then check for the
presence of the unique values first as done above, then check for the
presence of the duplicated values, discarding on non-matches.
Check first that b1 == d1. If no, cast aside this key. If yes, check
that b2 == d2. If no, cast aside this key. If yes, check that b3 == d3.
If no, cast aside this key, if yes - now time to check the redundant
values.
So if the time needed to check a check an 8 bit byte is less than the
time to check the entire 64bits of candidate plaintext against the known
plaintext, then the time spent checking plaintext-decrypted plaintext
matches for the large number of non-matching keys is minimized.
Is there a flaw in this approach that I missed?
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: BENNY AND THE MTB?
Date: Sun, 05 Nov 2000 21:31:32 GMT
Tim Tyler wrote:
> Bryan Olson <[EMAIL PROTECTED]> wrote:
> : Tim Tyler wrote:
> :> What you are now talking about has nothing to do with what
> :> Joseph Ashwood was talking about.
>
> : Not true. [...]
>
> I think it's true. How else can you eplain that he stated that the
> decryption of the cyphertext is one of 2^120 blocks? Joseph was
> discussing a system that no-one ever proposed - and which would
> not work.
The way I understand Ashwoods posts, he was showing that
no system that typically worked as described in David
Scott's story could exist. He was refuting Scott, not
Timmermans.
> : David faked the example to make the ciphertext come out as one byte.
>
> I wouldn't dispute that - but that seems to have nothing to do
> with what we're discussing.
It means that Matt's system, clever as it is, is not a
counter-example to Ashwood's argument that no such system
can exist. A real example would not have come out that
way.
> : Joseph Ashwood correctly concluded that the story is
> : nonsense, since if the system typically produces one-byte
> : plaintexts, one would have no way of knowning which of
> : 2^120 blocks to give to Rijndael.
>
> Your numbers appear to be faulty. If the system produces
> one byte cyphertexts (which it does), there's only 256 blocks
> to give Rijndael that produce this result (under a given key)
> - and Joseph's statement was based on a misunderstanding of
> how the system worked.
>
> The 2^120 figure comes from a non-existent system, which is
> not the one under discussion.
Again, Ashwood was not talking about the specifics of Matt's
system. He was showing that a system that worked as described
in the story _had_ to be non-existant.
The numbers are not faulty. As I wrote, not knowing which of
2^120 possibilities to use is basically the same problem as
depending on a 1/2^120 chance.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Brute force against DES
Date: 5 Nov 2000 21:46:17 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
John A. Malley wrote:
>If the plaintext block of eight, 8-bit bytes consists of 8 different
>values - b1, b2, b3, b4, b5, b6, b7, b8 - then when checking the
>candidate plaintext resulting from trial decryption with candidate key K
>- d1, d2, d3, d4, d5, d6, d7, d8 - check first that b1 == d1. If not,
>throw away this key.
But this is a very weak test: Over 89% of all incorrect key guesses
will survive this test.
Also, it requires knowing something about the byte-repetition patterns
in the plaintext, a questionable assumption. (Otherwise, you might discard
the correct key value.)
Compare to the following heuristic: If the high bit is set in any of
the bytes of the decryption, throw away this key. This eliminates
all but .4% of the wrong key guesses, and is a reliable test. (It
requires not much knowledge of the plaintext, and has a very low chance
of discarding correct keys when the plaintext is, e.g., ASCII English.)
Thus, even the very simple high-bit heuristic seems to be more effective
than a heuristic based on repeated bytes.
For strategies that are even more effective (yet still quite simple to
implement), you might take a look at the following paper:
A programmable plaintext recognizer, David Wagner and Steven M. Bellovin.
http://www.cs.berkeley.edu/~daw/papers/recog.ps
------------------------------
From: [EMAIL PROTECTED] (Anwar Hasan)
Subject: Re: ECC choice of field and basis
Date: 5 Nov 2000 21:58:47 GMT
The Oct issue of the IEEE Transactions on Computers has an
article on a hardware implementation of a versatile GF(2^m) processor.
It reports GF(2^192) multiplication and inversion times
as 2.41 and 4.81 micro-seconds at 75 MHz. It processor
can add two GF(2^191) elliptic curve points in about 25micro-sec.
-AH
In article <Mo%L5.12208$[EMAIL PROTECTED]>,
Michael Scott <[EMAIL PROTECTED]> wrote:
>
><[EMAIL PROTECTED]> wrote in message news:8tpumv$hd9$[EMAIL PROTECTED]...
>> Hello,
>>.....
>> 1) What are the advantages and disadvantages of choosing GF(2^m) or
>> GF(p) (and why not GF(p^m) in general)?
>>
>
>Good questions. Generally, and rather surprisingly, GF(p) is significantly
>faster in software, not pushed by any commercial interest, much less subject
>to patents. GF(2^m) is faster in special hardware, certain interests are
>pushing it hard, and is more likely to involve patents. Some restricted
>variants of GF(2^m) curves allow fast implementations, but some of these
>have been found to be weak (giving the whole field a bad name).
>
>> 2) What are the advantages and disadvantages of choosing polynomial
>> basis or optimal normal basis? Where can I find a good description of
>> optimal nornmal basis?
>>
>
>Polynomial basis faster in software. Optimal normal basis (if one exists)
>faster in hardware. Do a Web search for IEEE P1363 (which has been trying to
>standardise various PK technologies) for more information. Also I think
>P1363a covers GF(p^m) curves.
>
>
>Mike Scott
>
>Fastest is best.
>MIRACL multiprecision C/C++ library for big number cryptography
>Free implementations of Schoof's Algorithm for Elliptic Curves
>http://indigo.ie/~mscott
>
>> Any references?
>>
>> Thank you all.
>>
>>
>> Sent via Deja.com http://www.deja.com/
>> Before you buy.
>
>
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Microsoft's script encoder
Date: Sun, 05 Nov 2000 23:04:46 GMT
Ichinin wrote:
> Except where such license agreements are nullified by law...
IANAL, but last I looked (Prolock v. Copywrite), copyrighted software can be
reverse engineered, because copyright is federal law and contract law trying
to prevent it is state law. USA, of course, and may be out of date. I'd be
interested to hear if something has changed this.
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
The tragedy of the commons applies to monitizing eyeballs, too.
------------------------------
Date: Sun, 05 Nov 2000 16:32:35 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Brute force against DES
John A. Malley wrote:
>
> Francois Grieu wrote:
> >
> > "John A. Malley" <[EMAIL PROTECTED]> wrote :
> >
> > > Given plaintext and corresponding ciphertext, and (assuming) the
> > > ciphertext is in ECB form (no chaining), consider using redundancy
> > > in the plaintext (if present) to speed up the search for the
> > > correct key.
> >
> > I do not get it at all. Assuming one gets a known plain-ciphertext
> > pair, all there is to do is find a key (probably there is
> > only one) that maps the two. Redundancy of the plaintext is
> > perfectly useless.
>
> The mistake in explanation is mine. What I should have said is:
>
> The less redundant the plaintext, the faster the comparison between
> known plaintext and candidate plaintext resulting from trial decryption
> of the ciphertext with a candidate key.
>
> If the plaintext block of eight, 8-bit bytes consists of 8 different
> values - b1, b2, b3, b4, b5, b6, b7, b8 - then when checking the
> candidate plaintext resulting from trial decryption with candidate key K
> - d1, d2, d3, d4, d5, d6, d7, d8 - check first that b1 == d1. If not,
> throw away this key. There is no need to check the remainder of the
> decrypted output against the remainder of the known plaintext. This
> reduces the time spent verifying a key.
>
> If b1 == d1 then check if b2 == d2. If not, stop and throw the key away.
>
> If the plaintext contains several identical byte values and several
> unique byte values - b1, b2, b3, b4, b5, b4, b4, b5 - then check for the
> presence of the unique values first as done above, then check for the
> presence of the duplicated values, discarding on non-matches.
>
> Check first that b1 == d1. If no, cast aside this key. If yes, check
> that b2 == d2. If no, cast aside this key. If yes, check that b3 == d3.
> If no, cast aside this key, if yes - now time to check the redundant
> values.
>
> So if the time needed to check a check an 8 bit byte is less than the
> time to check the entire 64bits of candidate plaintext against the known
> plaintext, then the time spent checking plaintext-decrypted plaintext
> matches for the large number of non-matching keys is minimized.
>
> Is there a flaw in this approach that I missed?
>
Basically, you forget that most processors now are at least 32-bit. So
the computer would test 4 bytes all at once, and any process that tried
to test them individually would actually force more tests to be made.
Nonetheless, the flaw in any "brute force" strategy will not be
compensated by any such optimization. If you have to test billions of
keys, instead of thousands, you are going to be forever doing it -- no
matter how cleverly you test those billions.
To be effective, a deciphering algorithm must be able to break-down the
problem, eliminating entire possibilities for each key-byte (or more) so
that they do not have to be tested at all. Likewise, the cipher must be
designed so that this cannot be done... provably, cannot be done.
------------------------------
Date: Sun, 05 Nov 2000 16:34:57 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Microsoft's script encoder
Plus, in this case, I'm reminded of the fable of "The Emperor's New
Clothes." You cannot cover the emperor's posterior by passing a decree
which says that you are not allowed to reveal to him that he is naked.
It would be quite foolhardy to seek to protect your intellectual
property against disclosure and/or tampering using an algorithm whose
details, and security or lack thereof, you did not know -- and by some
strange decree, were told you could not discover.
>Darren New wrote:
>
> Ichinin wrote:
> > Except where such license agreements are nullified by law...
>
> IANAL, but last I looked (Prolock v. Copywrite), copyrighted software can be
> reverse engineered, because copyright is federal law and contract law trying
> to prevent it is state law. USA, of course, and may be out of date. I'd be
> interested to hear if something has changed this.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: BENNY AND THE MTB?
Reply-To: [EMAIL PROTECTED]
Date: Sun, 5 Nov 2000 23:27:00 GMT
Bryan Olson <[EMAIL PROTECTED]> wrote:
: As I wrote, not knowing which of 2^120 possibilities to use is
: basically the same problem as depending on a 1/2^120 chance.
Ashwood said:
"If you chop all but 8-bits of a Rijndael block, the decryption is one of
2^120 possibilities."
Chopping all but 8 bits from a Rijndael block - i.e. performing a
truncation, discarding all the other bits, whatever they may be,
is /not/ the scheme under discussion.
This scheme is not Matt's scheme - nor was it mentioned by David - who
stated that the scheme in use was Matt's scheme.
It is not the same as attempting to produce a 8-bit cyphertext from
Matt's program by attempting 2^120 encryptions.
Under Matt's scheme, if you have an 8 bit cyphertext, the decryption is
is one of 2^8 possibilities - *not* one of 2^120 possibilities.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: BENNY AND THE MTB?
Reply-To: [EMAIL PROTECTED]
Date: Sun, 5 Nov 2000 23:39:42 GMT
Matt Timmermans <[EMAIL PROTECTED]> wrote:
: Yes, Bryan's analysis is correct.
: All zeros counts as a finitely odd stream [...]
AFAIK, you are responsible for inventing this terminology - so I hesitate
to tell you what I think of it.
I liked David's definition of a finitely odd file - where 0 is not
included.
Any definition which includes the word "odd" and includes the
number 0x00000000 is highly counter-inutitive.
"Finitely odd" should refer to streams which terminate in a 1 followed by
an infinite string of zeros, IMO.
If a term for finitely odd files which /includes/ zero is desirable,
I believe the emphasis should be on the trailing zeros, rather than the
last 1. "Zero tailed", perhaps.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: [EMAIL PROTECTED] (Scott Craver)
Crossposted-To: talk.politics.crypto,talk.politics.misc,alt.freespeech
Subject: Re: Crypto Export Restrictions
Date: 5 Nov 2000 22:09:43 GMT
Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote:
>
>Like I said, if you do not have the intelligence and the energy and
>the interest to read the Help Files and have all your questions
>answered then just forget about it.
I read them. Still no pseudocode nor source code. And
you keep dodging the question: _which_ help file contains
the pseudocode? Which one?
>Since you have demonstrated that you will not even devote the time
>and energy to read the Help Files you clearly don't know what you
>are talking about regarding OAP-L3.
If someone is going to do you the favor of analyzing your
system, you should at least do them the favor of providing
psuedocode for the algorithm.
Insisting that people must reverse engineer the system
from vague descriptions help files? Sounds like animosity
towards cryptanalysts. Sounds like you're not very keen
on letting people analyze your system.
>Anyone who uses encryption software that does not generate pure
>random numbers is nutty if you ask me.
YOUR ENCRYPTION PROGRAM DOES NOT GENERATE PURE RANDOM
NUMBERS. It takes hopefully random numbers as input,
but probably horribly misuses them.
Why not take those beans or those cards and use them as
a seed for RC5? This has been thoroughly tested, and
designed by an expert. And the algorithm is well
documented.
Much more likely to be secure than some shuffling program
written by someone who does not know about permutation
groups.
>OAP-L3 requires true random number user input then generates pure
>random numbers for encryption purposes.
If the output is larger than the input, OAP-L3 (provably)
does not generate "pure random numbers." You can not
increase the amount of entropy in data.
>But you say this is nutty.
It's fraudulent, is what.
-S
------------------------------
From: [EMAIL PROTECTED] (Scott Craver)
Crossposted-To: talk.politics.crypto,talk.politics.misc,alt.freespeech
Subject: Re: Crypto Export Restrictions
Date: 5 Nov 2000 22:14:35 GMT
This is worth quoting again:
Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote:
>
>OAP-L3 requires true random number user input then generates pure
>random numbers for encryption purposes.
>
>But you say this is nutty.
OAP-L3's output is larger than it's input, and the output
is entirely derived from it. Hence it is in fact nutty.
The program can not output more bits of randomness than
is input.
-S
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Rijndael 128/192/256 implemented in GPG 1.0.4
Date: Mon, 06 Nov 2000 01:04:16 GMT
In article <[EMAIL PROTECTED]>,
David Crick <[EMAIL PROTECTED]> wrote:
> See http://www.gnupg.org/ for source code and binary distributions.
Is GNUPG more secure now right?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.hacker,talk.politics.misc,alt.freespeech
Subject: XOR Software Utility (freeware) available from Ciphile Software
Date: Sun, 05 Nov 2000 17:12:37 -0800
XOR Software Utility (freeware) available from Ciphile Software
This software simply performs the universally available logical XOR
process on two files chosen by the user and outputs the resulting
file.
http://www.ciphile.com
goto the Downloads Currently Available web page.
scroll to the bottom of the page.
Click on the blue anchor tag: CiphileXOR_10.zip (155kb)
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: BENNY AND THE MTB?
Date: Mon, 06 Nov 2000 01:29:09 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> AFAIK, you are responsible for inventing this terminology - so I hesitate
> to tell you what I think of it.
I can take responsibility for that, yes. I assume you think it sucks. Oh
well -- It's too late to change now, and it's intuitive to me. What is the
"oddness" of 0? Certainly less than the "oddness" of 1. Since 1 is
finitely odd, then 0 must be too.
The term made a lot of sense in the context in which it was coined:
The arithcoder writes a finitely odd binary number in [0,1)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Birthday messages
Date: Sun, 05 Nov 2000 20:44:06 -0500
Steve Portly wrote:
> For a 2000 character note written in English, what is the approximate
> key length that would produce more than one valid plain text message
> in a brute force attack? If the message is written in Japanese??
Brute force attack has nothing to do with whether or not multiple
valid plaintexts could produce the observed ciphertext using
appropriate keys. You neglected to say what cryptosystem, but
assuming that it is a good one, the question becomes one of the
chance of a *random* choice of 2000 characters forming a valid
plaintext, multiplied by the total possible number of keys. One
can use various models of the natural language to estimate the
former; the latter is easily found as the key-length power of the
size of the key "alphabet". The answer will be that the key length
has to be something like 2000 minus the unicity distance for the
natural language. I.e. over 1900 characters in the key.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: hardware RNG's
Date: 06 Nov 2000 01:49:25 GMT
David Schwartz wrote:
>
>Tim Tyler wrote:
>
>> This is not my field. However, are you sure that the drift is
>> unpredictable - and does not reflect environmental conditions
>> (such as temperature) which might be measured or controlled?
>
>They are correlated with temperature, but tiny fractions of a degree
>over small areas.
...The short term variations are affected by capacitance at the leads,
impedence of the driver, mechanical stresses on the crystal, etc.
In addition there is a long term effect as the crystal ages.
>Remember, we are dealing with cases where you can measure a part per
>billion.
Only a part per billion? Pretty sloppy measuring, by my standards.
------------------------------
** 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
******************************
