Cryptography-Digest Digest #874, Volume #8 Sun, 10 Jan 99 05:13:03 EST
Contents:
Re: RSA-Modulus decomposition (David Hamilton)
Re: Practical True Random Number Generator (Matthew Skala)
Re: Help: a logical difficulty (Dik T. Winter)
Re: Birthday Attack calculations. (Fred Van Andel)
Re: Birthday Attack calculations. (Fred Van Andel)
Re: Twofish vs DES? (Matt Curtin)
Re: What is left to invent? (Nicko van Someren)
Re: Twofish vs DES?
Re: Twofish vs DES? (JPeschel)
Re: Help me with this crypto ! (Nicol So)
Re: Twofish vs DES? ([EMAIL PROTECTED])
DH is "stronger" than RSA? ([EMAIL PROTECTED])
--- sci.crypt charter: read before you post (weekly notice) (D. J. Bernstein)
Re: On leaving the 56-bit key length limitation ([EMAIL PROTECTED])
----------------------------------------------------------------------------
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 22:25:14 GMT
=====BEGIN PGP SIGNED MESSAGE=====
[EMAIL PROTECTED] wrote:
(snip insults - which means snip all of it)
Two simple questions for David A. Scott.
1) Did you say you would crack IDEA?
2) Have you cracked it yet?
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
iQEVAwUBNpfW1so1RmX6QSF5AQENfwf8DGRN4Ip//bE02plLlca7Ve1RUGy+11hJ
8JBJjJ5e2rzjnbvSfM6ZTpGVL4bn6imMzo9icyrYJNRaeIa4gISFTvZismYbKndQ
8NK6scQGAjIrJi2kNoIqhnVkZv5TLadli0tR102FIG/31i29sGWU9filJE1IWdXu
D8G7Eob33rGM08EeG7hk+FdTT17XDqfT6iU9vyT437UCNehUm37Ejzfsn3d1jFxq
OiKlp4ME0q89HJ0514xUiwCtiP1MHKCBMuZhJwZev8CY06jxQK3Kb+V0qQjam1ik
nsrtzokhWjNZuZm4RtnnO1SsfHhIGdoHKr1sNYKAaFiXVZZq1/PLPQ==
=NiZ+
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: Practical True Random Number Generator
Date: 9 Jan 1999 15:45:04 -0800
In article <[EMAIL PROTECTED]>,
Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
>We'd also have to be careful that the sensors do not influence the
>molecules being measured. Devices this small would be smaller even than
I think that may be an impossible goal because of the Maxwell's demon
paradox - if you could measure gas molecules without affecting them, you'd
be able to build Maxwell's demon and that's Not Allowed. Perhaps someone
who knows the physics better can elucidate.
That may not be a bug, but rather a feature - if the molecular motions are
unpredictable, that's part of the goal, isn't it? Unfortunately, the
motions would also be so small as to be effectively impossible to measure,
at least cheaply.
We aren't really at a loss for good hardware random number generators.
Diode hiss works just fine - yes, you have to shield it carefully, but the
same would be true of anything that depends on a small-scale phenomenon,
and large-scale phenomena tend to be too predictable. So why make extra
work for ourselves with exotic sensing devices when something simple
would be just as good?
--
The third girl had an upside-down penguin on Matthew Skala
her stomach, so the doctor told her, "I'll Ansuz BBS
examine you for free, if you and your (250) 472-3169
boyfriend will debug my Web server." http://www.islandnet.com/~mskala/
------------------------------
Crossposted-To: sci.math
From: [EMAIL PROTECTED] (Dik T. Winter)
Subject: Re: Help: a logical difficulty
Date: Sun, 10 Jan 1999 02:22:42 GMT
In article <776hmi$5gi$[EMAIL PROTECTED]> [EMAIL PROTECTED] (Mike
McCarty) writes:
> Dictionary order is a complex and interesting topic, though no much
> related to mathematics. For example, consider my name, McCarty, and that
> of a friend of mine, MacDougal. Which of them comes first in dictionary
> (or, equivalently, alphabetical) order? MINE!
Depends on the language I would say. In our phonebook you would follow
your friend, sorry. But dictionary order is also a specific Computer
Science term and means first ordering by first element, next by the
second element. Even the collating sequence for the elements is
unspecified.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
------------------------------
From: [EMAIL PROTECTED] (Fred Van Andel)
Subject: Re: Birthday Attack calculations.
Date: Sun, 10 Jan 1999 02:50:03 GMT
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] wrote:
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
>> [EMAIL PROTECTED] wrote:
>
> snip...
>
>
> Then run 100 cases after your done with your low level
>testing. I you can't run 100 cases your method sucks.
>if you get any collisions at all in the 100 cases then you
>FUCKED up the CODE. But you MUST check the code for some
>cases that you actually suspect the code to run on.
> It reminds me of work when we bought code that was to run
>on a DEC machine using VT100 terminals. THE CRAP didn't work
>we talked to the company on phone several times. They claimed
>it was developed on DEC machines using VT100 terminals after
>months when one of there representatives came out to our site
>after several visits they brougth one of there VT100 termainals
>the CRAP ran. But they had used a VT100 clone there code
>would not work on a real VT100 DEC terminal. I think the
>company died I sure hope so. But you have to run REAL TESTS
>on the real one you expect the code to be used. Even if your
>a pompous asshole and irrigantly expect no problem.
>
There is not enough computing power on the planet to do a full
collision test on a 256 bit hash. Do the math yourself.
>
> You can expect all you want. Yor should more like a manager than
>a real programmer with much common sense.
I think there is an insult in there somewhere, I guess that means I
have arrived.
Fred Van Andel
------------------------------
From: [EMAIL PROTECTED] (Fred Van Andel)
Subject: Re: Birthday Attack calculations.
Date: Sun, 10 Jan 1999 02:50:21 GMT
Reply-To: [EMAIL PROTECTED]
"Trevor Jackson, III" <[EMAIL PROTECTED]> wrote:
>> 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.
Lets see if I understand you correctly. First you generate a pair of
hashes and compare them to each other. If they don't match then you
throw them away and generate a new pair. Repeat until you find a
match.
But by this method each pair only has one chance in N of being a
collision and therefore would require N/2 total comparisons to reach
the 50% level. When we are talking large hashes this becomes a hugh
number.
Another way is to generate all the hashes up front, sort them and then
compare. For example with a 64 bit hash you could generate your 1.2 *
2^32 hashes and save them to a file. Sorting the file will take
roughly 32 * 2^32 compares for a total of approx 2^37 operations.
This is much more feasible that the 2^63 operations required when
testing pairs of data. You could run approximately 2^26 of the
sorting tests in the same time as it takes to run one of the pairs
test.
Bear in mind that this method does not give you the average but rather
how often you are successful at the 50% level. This is a slightly
different number. If you want the true average you must generate more
numbers and then determine afterwards where the match occurred.
You refer to 2^79 compares required for a 40 bit hash. This the
absolute worst case in which no collisions are generated even after
all possible hashes have been created. The odds of reaching the end
of the hash without a collision are extremely remote. Even for a hash
as small as 8 bits, the odds of generating all possible hashes without
a collision is about 1 in 10^110. For our 40 bit example most of the
cases will cluster around 20 bits that corresponds to about 2^39
compares. That is much more manageable.
------------------------------
From: Matt Curtin <[EMAIL PROTECTED]>
Subject: Re: Twofish vs DES?
Date: 09 Jan 1999 21:23:52 -0500
"TERACytE" <[EMAIL PROTECTED]> writes:
> Which is better? Twofish or DES?
Consider that Twofish is being considered for AES, the standard to
replace DES...
--
Matt Curtin [EMAIL PROTECTED] http://www.interhack.net/people/cmcurtin/
------------------------------
From: Nicko van Someren <[EMAIL PROTECTED]>
Subject: Re: What is left to invent?
Date: Sun, 10 Jan 1999 03:20:16 +0000
This is a multi-part message in MIME format.
==============5E13849FFB168B5C5C79F6AE
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Darren New wrote:
> We already have
> ...
> , what's left to be invented?
An efficient reproducible Random Oracle.
Nicko
(For those out there unfamiliar with the term, a random oracle
is a mythical device which when presented with a question it
gives a truly random answer, with the proviso that if the question
has been asked before it gives the same answer as last time.
Many crypto proofs are only really proofs if your hash functions
are random oracles. You can build the prefect stream cipher
with a random oracle just by putting your key into a counter,
taking the output of the counter into the RO, and using the
output of the RO as the cipher pad. You can also make
unbreakable block ciphers using ROs. Very handy things, but
no one has ever made one.)
==============5E13849FFB168B5C5C79F6AE
Content-Type: text/x-vcard; charset=us-ascii;
name="nicko.vcf"
Content-Transfer-Encoding: 7bit
Content-Description: Card for Nicko van Someren
Content-Disposition: attachment;
filename="nicko.vcf"
begin:vcard
n:van Someren;Nicko
x-mozilla-html:FALSE
org:nCipher Corporation Ltd.<br><img
src="http://www.ncipher.com/images/masters/ncipher100.jpg">
version:2.1
email;internet:[EMAIL PROTECTED]
title:Chief Technology Officer
tel;fax:+44 1223 723601
tel;work:+44 1223 723600
adr;quoted-printable:;;Jupiter House=0D=0AStation Road;Cambridge;;CB1 2JD;England
x-mozilla-cpt:;0
fn:Nicko van Someren
end:vcard
==============5E13849FFB168B5C5C79F6AE==
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Twofish vs DES?
Date: 10 Jan 99 02:57:51 GMT
TERACytE ([EMAIL PROTECTED]) wrote:
: Which is better? Twofish or DES?
DES has been around for longer, so it is better known to be free of
mathematical weaknesses. (It has a few minor ones, however.)
Twofish, however, has a larger block size and, more importantly, a larger
key size. The key size of DES _is_ inadequate. Twofish, and several other
AES candidates, have been subjected to a reasonable amount of intensive
study, and thus Twofish is not likely to be seriously flawed.
John Savard
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Twofish vs DES?
Date: 10 Jan 1999 05:05:33 GMT
>[EMAIL PROTECTED] writes, in part:
>NEITHER
>if you want something more modern than these weak
>old ciphers
This is nonsense, David.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Help me with this crypto !
Date: Sat, 09 Jan 1999 22:45:49 -0500
Actually, I've seen a device that fits your description. It's a token
for challenge/response authentication. When you use it for remote
login, the remote system presents you with a "challenge" in the form of
an 8(?)-digit number, which you'd enter into the token for the proper
response.
Are you trying to reverse engineer the box?
Nicol
[EMAIL PROTECTED] wrote:
> > > I need some help with this crypto (or algorithm).
> > > I have a special box where you input some numbers and the box give you
> > > some numbers back.
> >
> > C'mon, we need more information than this. What sort of box? With wires
> > in it? How do you input the numbers? Switches?
>
> No, its looks/acts like a standard calculator without + - * / = keys.
>
> > > (if i input these numbers i always get the same output)
> > >
> > > PS. Could it be randomly generated numbers ??
> >
> > Well...not if you're always getting the same results..
> >
>
> Actually, it could be random numbers, because after every input
> i must press the enter-key and then i get the output number.
>
> After that the box could intialize the random generator so it always is
> using the same random pattern.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Twofish vs DES?
Date: Sun, 10 Jan 1999 03:43:27 GMT
In article <778jsh$[EMAIL PROTECTED]>,
"TERACytE" <[EMAIL PROTECTED]> wrote:
> Which is better? Twofish or DES?
>
>
NEITHER
if you want something more modern than these weak
old ciphers try something along the line of an all
or nothing type of encrytion for your files. If you
have an old machine use scott16u.zip If you have a
new faster machine then scott19u.zip might be a good
idea. Or fill free to change the source code which
is supplied with it.
ENJOY
:)
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://members.xoom.com/ecil/index.htm
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: DH is "stronger" than RSA?
Date: Mon, 04 Jan 1999 10:21:03 GMT
I am producing a FAQ for comp.security.pgp.discuss to explain the differences
between the old style RSA keys and the new style DH keys, along with all the
other cryptography related changes.
Obviously, I would like the FAQ to be as correct and up to date and, to this
end, I have a couple of questions related to recent papers.
E.Biham, D.Boneh, O.Reingold, "Generalized Diffie-Hellman modulo a composite
is not weaker than factoring", 1998. Implications: Does it prove that DH /
ElGamal cannot be a "weaker" problem than the IFP (and thus RSAP)?
D.Boneh, R.Venkatesan, "Breaking RSA may not be equivalent to factoring",
Eurocrypt '98, Lecture Notes in Computer Science, Vol. 1233,
Springer-Verlag, 1998.
Implications: One of the goals of recent number theory research related to
cryptography is proving that DHP = DLP and RSAP = IFP. Recent work has helped
prove certain cases of the first, but this paper indicates that no such proof
may be available for the latter.
Thus, from a theoretical (if not practical) perspective, the DHP (and thus
ElGamal) are appearing more long term secure than RSA (assuming that the
underlying problems IFP & DLP are equivalently intractable).
Am I anywhere near on the right track with this one?
Cheers in advance,
Sam Simpson
Comms Analyst
-- http://www.hertreg.ac.uk/ss/ for ScramDisk hard-drive encryption & Delphi
Crypto Components. PGP Keys available at the same site.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Crossposted-To: talk.politics.crypto
Subject: --- sci.crypt charter: read before you post (weekly notice)
Date: 10 Jan 1999 06:00:37 GMT
sci.crypt Different methods of data en/decryption.
sci.crypt.research Cryptography, cryptanalysis, and related issues.
talk.politics.crypto The relation between cryptography and government.
The Cryptography FAQ is posted to sci.crypt and talk.politics.crypto
every three weeks. You should read it before posting to either group.
A common myth is that sci.crypt is USENET's catch-all crypto newsgroup.
It is not. It is reserved for discussion of the _science_ of cryptology,
including cryptography, cryptanalysis, and related topics such as
one-way hash functions.
Use talk.politics.crypto for the _politics_ of cryptography, including
Clipper, Digital Telephony, NSA, RSADSI, the distribution of RC4, and
export controls.
What if you want to post an article which is neither pure science nor
pure politics? Go for talk.politics.crypto. Political discussions are
naturally free-ranging, and can easily include scientific articles. But
sci.crypt is much more limited: it has no room for politics.
It's appropriate to post (or at least cross-post) Clipper discussions to
alt.privacy.clipper, which should become talk.politics.crypto.clipper at
some point.
There are now several PGP newsgroups. Try comp.security.pgp.resources if
you want to find PGP, c.s.pgp.tech if you want to set it up and use it,
and c.s.pgp.discuss for other PGP-related questions.
Questions about microfilm and smuggling and other non-cryptographic
``spy stuff'' don't belong in sci.crypt. Try alt.security.
Other relevant newsgroups: misc.legal.computing, comp.org.eff.talk,
comp.org.cpsr.talk, alt.politics.org.nsa, comp.patents, sci.math,
comp.compression, comp.security.misc.
Here's the sci.crypt.research charter: ``The discussion of cryptography,
cryptanalysis, and related issues, in a more civilised environment than
is currently provided by sci.crypt.'' If you want to submit something to
the moderators, try [EMAIL PROTECTED]
---Dan
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: On leaving the 56-bit key length limitation
Date: Sun, 10 Jan 1999 07:55:10 GMT
Ed Gerk wrote:
[...]
> As an estimate for the (small) plaintext space one may need if only
> 3-characters are used, one can start with the maximum number of 2^18
> cases if one includes all upper and lower case letters, space,
> pucntuation and numbers in a 64-character alphabet (to simplify
> calculations). Of course, one should now rate the entries according to
> trigram linguistic frequencies for English -- taken from general text
> or (better) from former texts of similar sources (e.g., electrical
> engineering, computer science, social, medical, etc.). Looking at
> usual trigram tables [Sha49], [Bek82], I would assume one can thus
> reduce the plaintext space to probably 12,000 cases for the most
> relevant English trigrams (the, ing, and, her, ere, ent, tha, nth,
> was, eth, for, dth, hat, she, ion, int, his,...) [Bek82]. The
> probability of occurrence decreases rapidly along such a list. For
> example, "the" is approximately 8x more probable than "his".
>
> But, it may get better (i.e., worse). Since most cipher systems begin
> with a "magic number" or a message begins with the usual "Received",
> "To:", "From:", etc., then it may be possible to further reduce the
> 3-character list, for the message beginning. Perhaps, down to 1,000
> cases as I can evaluate from 10x the variety in my own messages.
>
[...]
> Of
> course, the less entries one has, the less false alarms one may
> encounter.
The unicity distance is the least number of characters for
which we do not expect any false alarms.
> However, the less entries one has the more misses one may
> suffer. Given the cost of a false alarm, the cost of a miss, and their
> probabilities, which can be translated in detection theory in terms of
> accuracy and reliability [Ger98], one can calculate the best threshold
> (in terms of number of trigram entries) that will minimize costs.
Actually carrying out some calculations shows that 3 characters
will not resolve the DES key. Let's use Ed's estimate of 1000
reasonably probable 3-character messages, encoded into 3 bytes.
Decryption with an incorrect key results in a random three-byte
string, and 1000 of the 16777216 three byte strings we recognize
as English. Thus an incorrect key has a one in 16777.216 chance,
equivalent to a probability of 0.00005960464477539, of inducing
English plaintext. Of the 2^56 DES keys, we therefore expect
about 4294967296000 of them to decrypt a given three byte
ciphertext into three bytes of English plaintext. Unicity
distance has not been reached.
> Bryan's whole "example" does not make sense and the reason is
[...]
> So, not only is the "example"
> past the maximum possible unicity of a 56-bit cipher .. which is 20 bytes for
> compressed English ... but it is still "undecided" as it tops 23 letters
I suppose Ed would have something of a case, had I said my
example considered DES. But he made that part up. The claim
that 20 bytes is the maximum possible unicity distance for a
cipher with a key of 56 bits and language of compressed
English is incorrect. The unicity distance estimate for a
random cipher H(K)/D is a lower bound, not an upper bound on
unicity distance.
--Bryan
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** 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
******************************
