Cryptography-Digest Digest #153, Volume #12 Mon, 3 Jul 00 16:13:01 EDT
Contents:
Re: Encryption and IBM's 12 teraflop MPC...... (Tramm Hudson)
Re: A simple all-or-nothing transform (Mark Wooding)
An exotic number conversion scheme (Mok-Kong Shen)
Re: A simple all-or-nothing transform (Mok-Kong Shen)
Re: Hashing Function (not cryptographically secure) (Scott Nelson)
A thought on OTPs (Darren New)
Re: Compression & Encryption in FISHYLAND (Tim Tyler)
Re: A simple all-or-nothing transform (David A Molnar)
Re: Diffie Hellman Primes : Speed Tradeoff Q (Anton Stiglic)
Re: SCOTT19U.ZIP_GUY **** PLONK! **** ("Joseph Ashwood")
Security of this F-Function (Simon Johnson)
cray and time needed to attack (Mist)
Re: cray and time needed to attack ("Joseph Ashwood")
Re: cray and time needed to attack (JPeschel)
Re: An encryption protocol, version 2 (Ichinin)
Re: How Uncertain? ("Douglas A. Gwyn")
Re: Tying Up Lost Ends III ("Douglas A. Gwyn")
Re: DES Analytic Crack ("Douglas A. Gwyn")
Re: Use of EPR "paradox" in cryptography ("Douglas A. Gwyn")
Re: cray and time needed to attack (Doug Kuhlman)
Re: cray and time needed to attack (JPeschel)
Re: A thought on OTPs ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Tramm Hudson)
Subject: Re: Encryption and IBM's 12 teraflop MPC......
Date: 3 Jul 2000 16:09:27 GMT
[posted and cc'd to cited author]
<[EMAIL PROTECTED]> wrote:
> ... All of the ASCI machines, at least recent ones, have been fairly
> similar designes, ....
There are very few similarities between the ASCI Red and Blue machines.
One is a working design with dual cpu boards that are used as two separate
CPU's, of which four thousand are connected with a very fast message
passing network that is structured as a two dimensional mesh. The other
is a NUMA big-way SMP with horrible memory latencie for non-local access
patterns and a hypercube interconnect that only scales by powers of two.
The White machine is continuing in the Blue design of large scale SMP
and will likely encounter similar problems that prevent it from scaling
as well as it the theoretical peak numbers would predict.
Tramm
--
o [EMAIL PROTECTED] [EMAIL PROTECTED] O___|
/|\ http://www.swcp.com/~hudson/ H 505.323.38.81 /\ \_
<< KC5RNF @ N5YYF.NM.AMPR.ORG W 505.986.60.75 \ \/\_\
0 U \_ |
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: A simple all-or-nothing transform
Date: 3 Jul 2000 16:24:36 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > Ah. Now you encrypt twice. This offers no advantage over Rivest's
> > package transform, does it?
>
> How the comparison is, I have yet no definite opinion myslef, since
> the idea has just come to me. But if it is as good is Rivest's, then
> having an alternative is something useful, isn't it?
I've no idea whether it's as good. I've not sat down and analysed.
However, having an alternative is only useful if the original is
deficient. The package transform appears to be pretty much ideal,
really.
Hmm. Does anyone have any formal results about the package transform?
Or even a formal statement of the properties it's meant to possess?
-- [mdw]
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: An exotic number conversion scheme
Date: Mon, 03 Jul 2000 19:05:47 +0200
Conversion of a number (representing a bit sequence) as digits
in a base b1 to another base b2 could be of some use for
encryption processing, as discussed in the group some time back.
As I understand it, the underlying goal thereby is to achieve an
invertible mapping that is more or less non-linear in terms
of the digits. The following is certainly a rather extreme
and exotic transformation scheme of its kind. It is not meant
to be advantageous for common usage but rather as a hint
that similarly fairly weird conversion schemes may eventually be
designed und employed under special circumstances that could
justify their use.
We shall consider here only numbers V in [0, 2^n-1], since long
bit sequences can be divided into groups of n bits each.
Choose an arbitrary prime p > 2^n. For V equal to 0 or 1, we
leave its coding unaltered. For the remaining cases, the quotient
V/p has a regular continued fraction representation of the form
[0, c_1, c_2, ......, c_k]. The coding of V is then taken to be
the sequence c_1, ......, c_k.
M. K. Shen
============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: A simple all-or-nothing transform
Date: Mon, 03 Jul 2000 19:12:42 +0200
Mark Wooding wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > > Ah. Now you encrypt twice. This offers no advantage over Rivest's
> > > package transform, does it?
> >
> > How the comparison is, I have yet no definite opinion myslef, since
> > the idea has just come to me. But if it is as good is Rivest's, then
> > having an alternative is something useful, isn't it?
>
> I've no idea whether it's as good. I've not sat down and analysed.
>
> However, having an alternative is only useful if the original is
> deficient. The package transform appears to be pretty much ideal,
> really.
I have little doubt that there exist people who spend their vacations
every year at the same good place. In cryptogrpahy, having variability
is an advantage.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Hashing Function (not cryptographically secure)
Reply-To: [EMAIL PROTECTED]
Date: Mon, 03 Jul 2000 17:06:21 GMT
On 03 Jul 2000 07:22:35 GMT, [EMAIL PROTECTED] (Mack) wrote:
>>> Actually, a N-bit CRC has the property that the CRC's of two messages
>>> differ if the bit differences are confined to an area at most N bits
>>> in length.
>>> His hash has precisely that property, and in retrospect, it's not
>>> surprising: the last step is essentially a 64-bit CRC with the
>>> polynomial x**64 + 1 (!).
>>
>>I'm not so sure of the accuracy of your description of what an N-bit CRC
>>does... I challenge you to find two messages that differ by 2 bits,
>>with more than 16 bits between the differing bits, but which have the
>>same CRC16 value.
>>
>
>Since the CRC-16 and CRC-CCITT (0x11005 & 0x11021) both detect all
>2 bit changes that is impossible.
>
CRC-16 doesn't detect all 2 bit changes, only certain kinds of
2 bit changes.
>The code described is a CRC-64 with a bad polynomial. A simple
>64 bit checksum would probably work a little better ie. use addition
>mod 2^64 instead of mod 2. Speed for software would be the same.
>
For the vast majority of applications, a 32 bit additive checksum
would be better. Reducing it to a word size and performing a
rotate after each add is better still, and probably almost as
fast. (both would be pretty hard to do in hardware though.)
Note that the birthday attack is only relevant
when one needs to protect against finding _any_ collisions.
It was a given that security was not needed for this.
>The description of the function of CRC is accurate. A CRC will detect
>all changes confined to one block that is shorter than the CRC. But
>a good CRC will detect other errors better. ie 2 bit changes.
>
>Some CRCs are better than others even among the 'good' ie. primitive
>polynomials.
>
Primitive polynomials are neither necessary, nor sufficient for
a CRC poly to be "good." CRC-CCITT isn't primitive, but has several
other nice properties which make it a reasonable choice.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: A thought on OTPs
Date: Mon, 03 Jul 2000 17:05:57 GMT
It's often said that OTPs are provably secure, in that any CT can decrypt to
any PT with the appropriate key. I thought of another way to express this
that might make it easier to understand. (Someone else may have already come
up with this idea, too. I'm not even an amateur. :-)
What really distinguishes the key in an OTP from the message? Nothing.
So you send the spy out into the field with the cyphertext. When you want to
send her a message, you generate the key that will cause the cyphertext to
decrypt to the appropiate message, and send it along. Since any message can
be so created, it's clear that when the bad guys capture the cyphertext,
they have no way of knowing what the message is.
As I said, this doesn't really change anything, but for people who have
trouble seeing why the OTP is provably secure, the idea that the first thing
you generate is the cyphertext and the second thing you generate is the key
might be interesting.
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"We have large financial earlobes."
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Compression & Encryption in FISHYLAND
Reply-To: [EMAIL PROTECTED]
Date: Mon, 3 Jul 2000 17:17:21 GMT
Kurt wrote:
: Tim wrote:
> : If you can influence seed generation, observe factors that influence
> : it, buy or steal a book of keys, etc, etc, you may already have a good
> : deal of information about the key bits from which an attack can be launched.
This information reduces the effective keyspace. If the keyspace is
reduced sufficiently (say you know the key is one of these 1,000
alternatives), details of the compression or even the encryption algorithm
itself aren't going to help materially.
Not necessarily true:
For example, it's easy to visualise circumstances where the keyspace is
reduced so that a brute-force search would be possible is possible, but
fails for lack of a halting criterion that uniquely establishes the
correct plaintext. This might happen (for example) if the plaintext is
relatively short.
Use of a duff compression algorithm that allows automated key rejection
could mean the difference between hundreds of possible decrypts, and
determining the correct plaintext unambiguously.
A single byte of header information would be sufficient to produce this
effect.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ UART what UEAT.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: A simple all-or-nothing transform
Date: 3 Jul 2000 17:58:09 GMT
Mark Wooding <[EMAIL PROTECTED]> wrote:
> Hmm. Does anyone have any formal results about the package transform?
> Or even a formal statement of the properties it's meant to possess?
I don't know of any formal results on the package transform offhand.
I do know that Victor Boyko has several nice definitions of an
all-or-nothing transform and a proof that OAEP meets these definitions in
his paper on "On the Security Properties of OAEP as an All-or-Nothing
Transform" from CRYPTO '99. This would also be in his PhD thesis, at
http://theory.lcs.mit.edu/~cis/cis-theses.html
-David
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Diffie Hellman Primes : Speed Tradeoff Q
Date: Mon, 03 Jul 2000 14:06:56 -0400
Bob Silverman wrote:
>
> In article <8jeela$e5v$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > I'm implementing Diffie-Hellman for a client-server product. I
> > understand that in an ideal world, a new shared p and g are chosen for
> > each session.
>
> Your understanding is wrong, even for an ideal world. It is neither
> necessary or desired to have a new key for each exchange.
>
> If you want forward secrecy, you must use both an ephemeral sesssion
> key and a static, permanent key in combination.
>
> Generating the key pair is easy, but coming up with a
> > large (1024 or 2048 bit) p every time is prohibitively slow when we're
> > talking about potentially 100's of new sessions per hour.
>
> False. Generating a 1024 bit prime should take a few tenths of a
> second AT MOST if done correctly.
Hmmm, I was playing around with Open-SLL prime number generator.
Generating a 2048 bit strong pseudo-prime (you want a strong prime p =
2q + 1
in DH for different reasons, you also want to work in the subgroup of
size
q and preferably have g = 2 as a generator for that group) on a 500 MHz
PIII
took more than 15 minutes on average.
1024 bit primes took less time, but not a fraction of a second.
Anton
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: SCOTT19U.ZIP_GUY **** PLONK! ****
Date: Mon, 3 Jul 2000 11:04:26 -0700
Come on, don't do that, just think of it as humor, besides it's at least
more interesting than Szopa. Actually DS occassionally says something
interesting, occassionally comes up with something above a 3rd grade level,
occassionally gives us reason to believe he's a psychotic 9 year old, or
maybe to believe he just needs some psychological counseling, but I don't
think it's worth PLONKing him over. Just laugh and skim what he writes for
something worth thinking about, and ignore the personal insults he sputters
out, unless you're the target, then it's a right of passage.
Joe
"Guy Macon" <[EMAIL PROTECTED]> wrote in message
news:8jo49p$[EMAIL PROTECTED]...
> **** PLONK! ****
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Security of this F-Function
Date: Mon, 03 Jul 2000 18:12:46 GMT
I was asked by a friend to design a cheap and nasty encryption
algorithm for his computing project. I quick thought up this F
function, and i was wondering wether it was actually secure or not?
(Words are 32-bit)
Function F(a,b)
A=((A + B) >>> (a xor b) mod 32) mod (2^32)
B=((A XOR B) >>> (A + B) mod 32) mod (2^32)
F = (A+B) mod (2^32)
End function
N.b. >>> denotes a Right Cicular Shift.
Also, i have a funny feeling my addition of A & B isn't to clever,
should i trust my gut? :)
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Mist)
Subject: cray and time needed to attack
Date: Mon, 03 Jul 2000 18:42:07 GMT
i want to know how many time is need to a cray to crack a:
1� 128 bit key with idea
2� 1024 bit key with blowfish
3� 128 bit key with RSA
4� 1024 bit key with DH
a friend told me it need less than a week to crack a 128 bit IDEA key
with a cray, does its right?
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: cray and time needed to attack
Date: Mon, 3 Jul 2000 12:01:17 -0700
While my answers certainly shouldn't be considered definitive, they are very
rough estimates.
> 1� 128 bit key with idea
A whole bunch of time, longer than you and I combined will live
> 2� 1024 bit key with blowfish
While I have my doubts that blowfish supports key sizes this large, even if
you could break 128-bit IDEA in .000000000001 second it would take about
2000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000
years to complete the computations. And that's a long, long time.
> 3� 128 bit key with RSA
About as long as it would take you to count to 100
> 4� 1024 bit key with DH
Currently a period of a few decades to a few centuries (other people can
give you a much better idea of it). But remember we're always getting better
at it.
I hope my answers helped at least a little.
Joe
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: cray and time needed to attack
Date: 03 Jul 2000 19:06:37 GMT
[EMAIL PROTECTED] (Mist) writes:
>i want to know how many time is need to a cray to crack a:
>1� 128 bit key with idea
>2� 1024 bit key with blowfish
>3� 128 bit key with RSA
>4� 1024 bit key with DH
>
>a friend told me it need less than a week to crack a 128 bit IDEA key
>with a cray, does its right?
For numbers 1& 2 cracking will take much longer than you
(or anyone else) can possibly wait.
I think you should be able crack a 128-bit RSA key on a Cray pretty damn
fast.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: An encryption protocol, version 2
Date: Mon, 03 Jul 2000 21:04:19 +0200
Is it something like this?
http://www.patents.ibm.com/details?&pn=US05428686__
If it is, Somehow i don't think you'll be able to
challenge it (Hint: look at the assignee)
/Ichinin
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: How Uncertain?
Date: Mon, 3 Jul 2000 18:15:15 GMT
Tim Tyler wrote:
> But this is redundancy - surely the opposite of entropy in this context.
You're right, I was working from the opposite direction, where lack of
information constitutes a source of entropy.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Tying Up Lost Ends III
Date: Mon, 3 Jul 2000 18:19:49 GMT
"SCOTT19U.ZIP_GUY" wrote:
> After all is light a particle or a wave.
It seems to be a particle guided by a wave.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: DES Analytic Crack
Date: Mon, 3 Jul 2000 18:28:18 GMT
Mok-Kong Shen wrote:
> DES through solving a set of mathematical equations. However, it
> was found that that would require, among others, a practically
> impossible large amount of memory space.
If so, that was a miscalculation.
------------------------------
Crossposted-To: sci.physics
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Use of EPR "paradox" in cryptography
Date: Mon, 3 Jul 2000 18:30:10 GMT
John Savard wrote:
> However, the fact that one measurement affects the other,
> yet at a speed faster than light, ...
Not really, at witnessed by the fact that one cannot exploit
EPR to send controlled information faster than light.
------------------------------
From: Doug Kuhlman <[EMAIL PROTECTED]>
Subject: Re: cray and time needed to attack
Date: Mon, 03 Jul 2000 14:05:58 -0500
Mist wrote:
>
> i want to know how many time is need to a cray to crack a:
> 1� 128 bit key with idea
> 2� 1024 bit key with blowfish
> 3� 128 bit key with RSA
Not sure of the others, but I can do this one on my PC in about 3
seconds. ;-)
> 4� 1024 bit key with DH
>
> a friend told me it need less than a week to crack a 128 bit IDEA key
> with a cray, does its right?
The whole question kind of revolves around what you mean by "to crack",
what methods are being used, etc. Which Cray?
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: cray and time needed to attack
Date: 03 Jul 2000 19:47:01 GMT
Doug Kuhlman [EMAIL PROTECTED] writes::
>Mist wrote:
>>
>> i want to know how many time is need to a cray to crack a:
>> 1� 128 bit key with idea
>> 2� 1024 bit key with blowfish
>> 3� 128 bit key with RSA
>
>Not sure of the others, but I can do this one on my PC in about 3
>seconds. ;-)
>
>> 4� 1024 bit key with DH
>>
>> a friend told me it need less than a week to crack a 128 bit IDEA key
>> with a cray, does its right?
>
>The whole question kind of revolves around what you mean by "to crack",
>what methods are being used, etc. Which Cray?
>
I suppose he means recovering the symmetric keys by exhaustive
search of the keyspace, and the RSA and DH keys by factoring.
It's not going to matter much which Cray or how many Crays are being
used. Numbers 1,2, and 4 won't be solved any time soon, and there
isn't much point in throwing an army of Crays of any rank at a tiny 128
bit RSA number.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: A thought on OTPs
Date: Mon, 3 Jul 2000 18:36:16 GMT
Darren New wrote:
> As I said, this doesn't really change anything, but for people who have
> trouble seeing why the OTP is provably secure, the idea that the first thing
> you generate is the cyphertext and the second thing you generate is the key
> might be interesting.
More likely it is just confusing, since it abuses the standard
usage for the terms "key" and "ciphertext".
------------------------------
** 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
******************************
