Cryptography-Digest Digest #557, Volume #9 Mon, 17 May 99 14:13:04 EDT
Contents:
Re: Mandlebrot transform (Matthew Skala)
Feedback on free new DH/TEA encryption program I wrote in one night. (Nathan Kennedy)
Re: Keyed bit permutation (Matthew Kwan)
Re: Hello I am paper, please read me. ([EMAIL PROTECTED])
Re: Need to design basic authentication system (Mark Carroll)
Re: Hello I am paper, please read me. ([EMAIL PROTECTED])
Re: Security ([EMAIL PROTECTED])
Re: Computer-generated random numbers (was Re: Magic) ([EMAIL PROTECTED])
Re: Need to design basic authentication system (David P Jablon)
Re: Bricklaying DES (Piso Mojado)
Re: Security (David A Molnar)
QQ: Exporting SHA from the USA? (iLLusIOn)
Re: Hmm, I wonder if I got this right (Jim Felling)
Re: QQ: Exporting SHA from the USA? (DJohn37050)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: Mandlebrot transform
Date: 16 May 1999 20:15:30 -0700
In article <7hnqkv$hd7$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>This 'c' value is the output (usually the color) right?
No. You start the process with z=0, and c= the coordinates of the current
point on the screen. Then you iterate it (square z, add c, square z, add
c, and so on) until either z gets bigger than a set radius, or you've
iterated some maximum number of iterations. Then the color for the point
at location c, is the number of iterations you took. The Mandelbrot set
proper is the set of values c where the iteration does *not* escape to
infinity; those are often colored black. There are other things you can
do with this iteration, but what I've described is the standard
"Mandelbrot set" algorithm.
I don't think that the iteration z<-z^2+c is particularly interesting from
a cryptographic point of view when it's over the complex numbers. It
could maybe be of some use as a "mixing" step in a cipher if you did it
with integers modulo a prime.
--
Matthew Skala Ansuz BBS (250) 472-3169 http://www.islandnet.com/~mskala/
GOD HATES SPAM
------------------------------
From: Nathan Kennedy <[EMAIL PROTECTED]>
Subject: Feedback on free new DH/TEA encryption program I wrote in one night.
Date: Mon, 17 May 1999 17:17:31 +0800
I wrote this program a few weeks back at about 1 am in the morning. Since
then I have only added a touch or two, to make it preserve file-size and a
little other stuff. It basically just uses 1024-bit DH for key exchange
and XORs the lower (lease significant) 128 bits against a 128-bit random
session key, which is used as a 128 bit key to encrypt the data with TEA
using CFB (I think that's right) mode, with a 64 bit IV.
Naturally, it is very rough, probably shouldn't be used for anything
important, comes with zero docs except the code (which is all you get).
I'm giving it a version number of 0.1 This is not a finished product; it
is a lump of ugly code that compiles and runs.
The code was written under Linux but may compile under others. It requires
the gmp (Gnu Multiple Precision) library for arbitrary-precision
arithmetic, and uses /dev/urandom and /dev/random to get random bits.
First you'll have to compile it---
gcc -o natepub natepub.c -lgmp
Then you can test the encryption and decryption.
natepub mysec yourpub < sample > sample3
natepub yoursec mypub dec < sample3 > sample4
natepub yoursec mypub dec < sample2 > sample5
diff sample sample4
diff sample sample5
If the files compare, it should be working.
To generate your own keys, you just need to store them as a string of ASCII
decimal digits on one line. The secret key is chosen randomly, less than
the public modulus. Just raise 3 to your secret key modulus the modulus,
and that's your public key. The enclose powmod.lisp will make this easy.
The modulus for natepub.c is
1797693134862315907729305190789024733617976978942306572734300
8115773267580550096313270847732240753602112011387987139335765
8789768814416622492847430639474124377767893424865485276302219
6012460941194530829520850057688381506823424628814739131105408
2723716335051068458629823994724593847971630483535632962422579
5083
You can fetch the natepub suite at
http://inside.com.tw/user/kennedy/nate/natepub-0.1.tar.gz
Here are the md5sums:
3420ae9751efddd995161e38123e9b2a natepub-0.1.tar.gz
0636e73ff0215e8d672dc4c32c317bb3 natepub-0.1/COPYING
14e416bd3a5920b901d0a8b0182be648 natepub-0.1/modulus
c15f7a7875c4ebdd4092ffce66ade8ea natepub-0.1/mypub
d8cf998aa69e0110a1205d72e6206979 natepub-0.1/mysec
b9bdc50ec7c181af27112836a91a08ce natepub-0.1/natepub.c
3c889d7c30417865d623b75873f16dff natepub-0.1/powmod.lisp
0bfba2ea5261876fff792c3b0dd4a1c4 natepub-0.1/sample
3ec06c94f4fc72da0546b24990a8231e natepub-0.1/sample1
ee66288afc61eb0d4c2e28580aa2c523 natepub-0.1/teamac.h
df64ea1591b2a9465a0579df97138671 natepub-0.1/yourpub
0427f5e501ed95da0919ae83ec97792a natepub-0.1/yoursec
And here is the detached signature for natepub-0.1.tar.gz, available at
http://inside.com.tw/user/kennedy/nate/natepub-0.1.tar.gz.asc
=====BEGIN PGP SIGNATURE=====
Version: GnuPG v0.9.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org
iD8DBQA3P9y98WKagKsEr/ERAlAgAJsH/D4s35lLO7Ki+wuXrw/R/1PwUgCaA2qO
a2rlnhlniJqX4h4p6OlYhMU=
=KD22
=====END PGP SIGNATURE=====
There you go. I'll be waiting for your feedback and advice.
Nate
------------------------------
From: [EMAIL PROTECTED] (Matthew Kwan)
Subject: Re: Keyed bit permutation
Date: 17 May 1999 19:32:47 +1000
[EMAIL PROTECTED] (Christopher) writes:
>Oops, that should be seven NANDs per subkey bit, including the subkey bit
>inversion used twice.
>In article <[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] (Christopher) wrote:
> |:| Well, the keyed-permutation is efficient in hardware, eight NANDs per
> |:| subkey bit, three levels deep (including the inversion of the subkey
> |:| bit). And the final (fixed) permutation costs nothing in hardware.
> |:|
Actually, you can do it with 3 XORs and an AND. That's the way I
implemented it in the ICE source (http://www.darkside.com.au/ice).
Of course, it depends how efficiently you can implement XOR in hardware.
mkwan
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Hello I am paper, please read me.
Date: Mon, 17 May 1999 07:01:57 GMT
tomstdenis:
>
> > Look at the decks after 8 or 16 shuffles. It seems the reason
> > for the non-randomness is that if x and y are n apart before a
> > shuffle, there's a very good chance they'll be 2n % 256 apart
> > after the shuffle.
>
> So if you know the shuffling bisectors for all t shuffles (summed into
> n) you can predict the original starting points? Hmm, not good.
I thought the shuffling was supposed to produce a pseudo random
permutation. Did you actually look at the decks after 8 or 16
shuffles? You certainly don't need any shuffling bisectors to
notice the patterns.
--Bryan
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Mark Carroll)
Subject: Re: Need to design basic authentication system
Date: 17 May 1999 11:45:04 +0100 (BST)
In article <mXg%2.16606$[EMAIL PROTECTED]>,
Tim Mavers <[EMAIL PROTECTED]> wrote:
(snip)
>How does the server calculate that the data returned from the client (step 3
>above) is correct? It would seem that the server has to have a copy of the
>user's password in order to perform the hash(nonce,password), right? How is
Yes.
>the password initially exchanged then? Over the network? If so, that seems
For the first time the user is 'created', yes the scheme doesn't
address this.
>that someone sniffing could just pick apart the passwords and voila. They
>could then reply to the server's nonce calls in the future.
...but then again you only asked about the best way to allow a user to
log in via a name and password, a suggestion for which I gave. You
didn't ask about how the password was initially set, so don't be
amazed that I didn't address that!
If you want users to get their first password over the network, then
you have to think if any shared secret at all initially exists between
the user and server? (worry about man-in-the-middle attacks?) And, if
you start to apply public/private key cryptography, then you have to
think about how the user knows to trust the key server in the first
place - how do they know they have the real server's public key? As
well as it being important that they are authenticated to the server,
must the server also authenticate itself to them? (Your choice.)
Of course, in the real world, first-time passwords are very often
communicated either insecurely or in-person, as it's not a trivial
nut to crack. (-:
So, tell us more about the mode of deployment. Does any shared secret
at all exist between the user and server prior to the first password?
And is the network between them one that the attacker can listen in on
but not actually fiddle with, or what?
-- Mark
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Hello I am paper, please read me.
Date: Mon, 17 May 1999 11:42:50 GMT
> I thought the shuffling was supposed to produce a pseudo random
> permutation. Did you actually look at the decks after 8 or 16
> shuffles? You certainly don't need any shuffling bisectors to
> notice the patterns.
>
The problem is that trying to shuffle the deck with only one value will
always leave patterns. RC4 over comes this by using the deck as
paramters and the key (over and over).
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Security
Date: Mon, 17 May 1999 11:47:49 GMT
> This is part of your conjecture, or do you have some reasoning which
> leads you to this conclusion? I'm not sure I follow.
>
> Are you arguing that there are an unlimited number of algorithms to
> break ciphers, therefore there must be at least one algorithm for
> each AES candidate or other block cipher?
DES: nuff said.
> I'm hesitant to label an attack useless without making specific
> reference to an implementation and the design of an entire system.
> It is true that some attacks are a lot harder to apply than others,
> though. My concern stems from the fact that a lot of attacks I thought
> were sort of useless at first glance, like chosen-ciphertext attacks,
> end up being useful after all.
A useless attack would be a 2^43 chosen-plaintext against a file
encryptor. Or 2^62 operations (which take 1 second each), etc..
When DES came out they didn't think linear/differential analysis would
break it did they? They might not have known (until it was to late)
about the weak keys.
I would bet anything that in 20 years, there will exist some crack on
AES faster then brute force of the key, or ciphertext.
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
Date: Mon, 17 May 1999 08:44:24 -0400
From: [EMAIL PROTECTED]
Crossposted-To: rec.arts.sf.science
Subject: Re: Computer-generated random numbers (was Re: Magic)
Frank Palmer wrote:
>
> A good pseudo-random number generator evades the first problem,
> but never (for long enough runs) the second.
I believe this statement to be false. Clearly there is a limit to the
amount of sampling that can be performed on an RNG. If the period of
the RNG is longer than the maximum sample available then no periodicity
will be detectable.
------------------------------
From: [EMAIL PROTECTED] (David P Jablon)
Subject: Re: Need to design basic authentication system
Date: Mon, 17 May 1999 13:21:02 GMT
In article <mXg%2.16606$[EMAIL PROTECTED]>,
Tim Mavers <[EMAIL PROTECTED]> wrote:
>> In article <kLz_2.3608$[EMAIL PROTECTED]>,
>> Tim Mavers <[EMAIL PROTECTED]> wrote:
>>
>>> For a project I am working on, I need to design (and implement) a basic,
>>> secure user-authentication system that will allow a user on a client
>machine
>>> log into a "server" via a name and password.
>>>
>>> What is the best way of doing this? I was thinking of a
>>> challenge-response
Instead look at <http://IntegritySciences.com/speke.html>.
It's simple, and blocks all network "crack" attacks.
>Mark Carroll <[EMAIL PROTECTED]> wrote in message
>news:Avp*[EMAIL PROTECTED]...
>> A simple way is:
>>
>> Client -> Server : Username
>> Server -> Client : nonce
>> Client -> Server : Hash(nonce,Password)
>>
>> At least, it will defeat casual passive eavesdroppers (e.g. packet
>> sniffers) if you think of nonces well and try not to reuse any.
With this protocol, a passive eavesdropper can make
unlimited guesses for the password and often crack it.
> How does the server calculate that the data returned from the client (step 3
> above) is correct? It would seem that the server has to have a copy of the
> user's password in order to perform the hash(none,password), right?
Not necessarily. The server can store a hash of the password,
and the client can prove knowledge of the hashed-password instead
of the password. This simple trick can also be used with SPEKE.
A more sophisticated approach, used in B-SPEKE & SRP,
has the server store a DH public-key corresponding to a
password-derived private key.
======================================================
David P. Jablon
Integrity Sciences, Inc.
[EMAIL PROTECTED]
<http://www.IntegritySciences.com>
------------------------------
From: Piso Mojado <[EMAIL PROTECTED]>
Subject: Re: Bricklaying DES
Date: Mon, 17 May 1999 09:02:25 -1000
David Wagner wrote:
> Maybe I'm missing something, but this doesn't look like much of
> an improvement to me. It looks like there's a 2^56 attack.
>
> Consider a chosen-ciphertext attack where you twiddle just the first
> block of ciphertext somehow, decrypt both ciphertexts, and look at the
> first block P,P' of the resulting two plaintexts. They will satisfy
> DES(k1,P) xor DES(k1,P') = (?,0).
> In other words, the right half of the xor is zero. Here k1 is the
> 56-bit DES key used in the first round. This provides a way to do a
> divide-and-conquer attack that isolates the first DES key: you can do
> a keysearch, test the above relation, and with two such queries you
> can uniquely identify k1. Now peel off the first round and repeat.
>
> These chosen-ciphertext queries can often be implemented under the
> known-plaintext attack model, if you modify the first block while it
> is in transmission, and then get the plaintext the sender sent as well
> as the modified plaintext the receiver decrypts.
I disagree with your conclusion that half of ONE
plaintext block XOR would be zero, using only 2^56
guesses. But I am willing to be convinced otherwise
by more detailed explanations. Here is the bricklaying
scheme proposed, to review the set-up:
3 plaintext blocks are encrypted with 3 DES keys.
The resulting ciphertexts are rotated a half block
so that mixing occurs during the next round from any
one block into 2 blocks. A new key is used for each
DES encryption so for 3 rounds and 3 blocks wide, there
are 9 keys of 56 bits each.
Plaintext1 Plaintext2 Plaintext3
DES DES DES
Ciphertext1a Ciphertext2a Ciphertext3a
Right3a Left1a Right1a Left2a Right2a Left3a ROTATED
DES DES DES
Ciphertext1b Ciphertext2b Ciphertext3b
Right3b Left1b Right1b Left2b Right2b Left3b ROTATED
DES DES DES
Ciphertext1c Ciphertext2c Ciphertext3c
Your analysis is not correct because twiddling bits in the
final ciphertexts involves 192 bits that have come from
192 input bits that have diffusion between DES blocks. For
example, Ciphertext1c is from parts of Ciphertext1b and
Ciphertext3b that were encrypted with 2 keys in 2 blocks.
This bifurcation means Ciphertext1c is therefore derived from
Ciphertext1a, Ciphertext2a, and Ciphertext3a. Each 64 bit
output ciphertext is controlled by all 3 plaintexts using
504 key bits. The diffusion caused by bricklaying DES blocks
means that 2^56 guesses at ciphertexts will probably not
cause decryptions to result in XOR of two plaintexts having
half zero bits, as you stated. You need 2^192 guesses to be
sure to find an XOR of plaintexts with half bit being zero.
This Bricklaying technique is valuable for any block cipher,
not just DES. It gives people a way to increase the key and
text sizes easily. It is easy to understand and easy to
communicate the number of rounds and width of superblocks.
One could use 10 input blocks for 640 bit text width, and
10 rounds with up to 5600 key bits. The diffusion caused by
Bricklaying prevents the attack David Wagner described.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Security
Date: 17 May 1999 16:09:19 GMT
>> This is part of your conjecture, or do you have some reasoning which
>> leads you to this conclusion? I'm not sure I follow.
>>
>> Are you arguing that there are an unlimited number of algorithms to
>> break ciphers, therefore there must be at least one algorithm for
>> each AES candidate or other block cipher?
> DES: nuff said.
I'm sorry, I'm slow and still not following. :-\
Do you mean that because a better-than-brute-force attack for DES
was found after 20 years (and everyone thought it was 'safe'),
therefore a better-than-brute-force attack must exist against
all ciphers?
>> though. My concern stems from the fact that a lot of attacks I thought
>> were sort of useless at first glance, like chosen-ciphertext attacks,
>> end up being useful after all.
> A useless attack would be a 2^43 chosen-plaintext against a file
> encryptor. Or 2^62 operations (which take 1 second each), etc..
This is more to my liking because now we have some specifics and can
start reasonably saying that something is impractical.
I'd still want to know where this file encryptor is (if it's working
for one of those net backup companies, we have a problem), and if
those 2^62 operations can be distributed. :-)
> I would bet anything that in 20 years, there will exist some crack on
> AES faster then brute force of the key, or ciphertext.
I agree with you. We don't know nearly enough to say that no attack exists.
The track record suggests that some attack probably does.
My nitpicking comes from the belief that we don't even know enough to say
that some attack _must_ exist.
-David
------------------------------
Date: 17 May 1999 16:34:13 -0000
From: iLLusIOn <Use-Author-Address-Header@[127.1]>
Subject: QQ: Exporting SHA from the USA?
=====BEGIN PGP SIGNED MESSAGE=====
just a quick question, is it possible/allowed to
export a program using the SHA from the USA
(the program i'm talking about only uses SHA,
and no encryption algorithms with keysizes bigger
40 bits)?
tia
~~~
This PGP signature only certifies the sender and date of the message.
It implies no approval from the administrators of nym.alias.net.
Date: Mon May 17 16:34:11 1999 GMT
From: [EMAIL PROTECTED]
=====BEGIN PGP SIGNATURE=====
Version: 2.6.2
iQEVAwUBN0BFBE5NDhYLYPHNAQGB1wf+M9HCzbXmZ8Jc+zU2brtYXBYxIZmE+Sum
dnaWZR1yy4TYQt+lFPK+ywECZAvg7V6VHzu4KKVgdtMWf1QqSqND5EQcI5bA5C6o
+wZKrxEAs56O3ehg9M5TvVFsZhc9XYOHcnT8//LoyNxqkApVenSjerxvoci+gBhQ
jH7NAEFzsiagffq2T+qIF9fu4FGKcMWG+WFnyGL+NP1cuH5s+nI8x5eEqWogg833
RCzu8LJ3IunaThUz3eLchgowKSzExp/EBNyFZPioDMJxHu5BeRMlZNA3tCiz6/YW
zzN2hPt0zTrGqTFURaCdKBC1YeAT0LzSfLr8MYvB1+/TmEmkdMoBLA==
=Whrk
=====END PGP SIGNATURE=====
------------------------------
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Hmm, I wonder if I got this right
Date: Mon, 17 May 1999 12:36:17 -0500
[EMAIL PROTECTED] wrote:
> Am I right (I hope...)
>
> A differential attack is where you find a common delta dX in the input
> that satisfies a delta in the output dY with a higher (then equal)
> probility. From this subkeys can be suggested. If only a subset of the
> keyspace generates this, then one could find a suggested key faster
> then brute force.
>
> A linear attack tries to create some linear equation with a probabilty
> greater then 1/2, which maps a bit(s) from input->key->output. If this
> linear equation holds true, then the output/input can be elimiated from
> the linear equation leaving only the key.
>
> Questions
>
> 1) Does multiple approximations (linear) or deltas (differential) aid
> in the attack, or only the one with the highest probabilty.
Yes( in general) -- one can carry out multiple attacks in parallel feeding
the conclusions/ eliminated keys of one into another -- speeding the
process along greatly in some cases, and not helping at all in others
--usually this will be a productive tactic.
>
>
> 2) Can you predict which subset of the keyspace will bare true
> (greater then 1/2) for a given approximation or delta? I mean to ask,
> do you just try through brute force which keys will work?
I don't quite understand what you are asking. If you are asking how the
attacks are found/ carried out it is by carefully eyeballing the cypher and
seeing what looks likely as a means of attack and what does not look likely
as a means of attack and seeing if/how one can take advantage of that.
>
>
> 3) Can a cipher emit differences, and have the key undectable (or
> invalid for the most probable delta)?
I am not quite sure what you are asking here either. A differential will
not simply hand you the key, though it will make it much easier to
eliminate candidate keys and also to select promising keys. An existing
differential will have the effect of reducing the "real" keyspace. It will
at worst allow you to brute force more efficiently.
>
>
> 4) What is the mathematical method(s) for making linear/diff. attacks
> difficult?
>
>
> Thanks in advance,
> Tom
> --
> PGP public keys. SPARE key is for daily work, WORK key is for
> published work. The spare is at
> 'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
> 'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
>
> --== Sent via Deja.com http://www.deja.com/ ==--
> ---Share what you know. Learn what you don't.---
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: QQ: Exporting SHA from the USA?
Date: 17 May 1999 17:53:20 GMT
The answer depends on the capability of your system. Any crypto is a flag for
review of functionality.
Don Johnson
------------------------------
** 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
******************************
