Cryptography-Digest Digest #929, Volume #10 Wed, 19 Jan 00 13:13:01 EST
Contents:
Re: Questions about message digest functions ([EMAIL PROTECTED])
Re: MIRDEK: more fun with playing cards. (CLSV)
Re: New Crypto Regulations (JPeschel)
Re: Kryptos... Did they finish it? (Jim Gillogly)
Simple cipher to break for newbies ([EMAIL PROTECTED])
Re: New Crypto Regulations (wtshaw)
Re: New Crypto Regulations (wtshaw)
Re: MIRDEK: more fun with playing cards. ([EMAIL PROTECTED])
Re: Java's RSA implimentation (Bob Silverman)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Questions about message digest functions
Date: Wed, 19 Jan 2000 16:22:36 GMT
Tim Tyler wrote
> [EMAIL PROTECTED] wrote:
>
> : Actually the even distribution makes brute-force search for
> : a second preimage *easier*. Suppose we have a hash that
> : produces 160-bit digests that is a permutation (for messages
> : that are also 160-bits), and we need to find a collision
> : with a given message of any size larger than the digest. If
> : we search the space of 160-bit messages, we will find a
> : match in an average of 2^159 + 0.5 tries. That's almost
> : exactly a factor of two faster than against a random
> : function.
>
> This is an interesting point. I agree with the conclusion.
>
> If the attacker can choose any-sized message, having a bijective
> map between hashes and some clearly-defined group of messages
> seems to be undesirable.
You are convinced by the wrong arguments. Brute force
search is of no concern.
> :> While for smaller messages, it can become interesting
> :> - particularly when getting a beter distribution
> :> completely eliminates the has collisions that would
> :> otherwise occur.
>
> : As David Hopwood pointed out in hist post (worth re-reading)
> : of 12/30/1999, all that shows is that some applications call
> : for something other than a hash. It does nothing to redeem
> : your claim that the random function model is "dead wrong"
> : for cryptographic hash functions.
>
> It appeared to me that the "applications that call for something other
> than a hash" included signing messages and concentrating the
> entropy-per-bit of a random file.
Nonsense. The only case where an even mapping has a major
advantage is when the function is only defined for preimages
of the same size as the hash.
Understand that 1KB is a short. If we map perfectly evenly
to 160-bit digests, what is the probability of two random
1KB messages colliding?
There's no market for signature schemes restricted to
messages of a particular size. For concentrating entropy,
even if you had a perfectly even hash, it's only perfectly
even for a particular message space. If we design a hash so
that all digests have the same number of 1KB preimages,
that says nothing about how the distribution of files we
actually deal with will map. The random function model
works well for any input distibution.
[...]
> : You have yet to state your model. Obviously you want the
> : preimages to map evenly to the digests [...]
>
> Yes, exactly.
>
> : [...] but from what probability space of functions do
> : you think a hash should model a random choice? [...]
>
> This will depend on the application. I'm trying to define the best
> frequency-distribution of hashes in terms of the space of messages
> it can be expected to be fed.
Note that in my question, when I wrote "hash" I meant a
function, not a digest. The random function model describes
much more than this one frequency graph.
> This may well be different in different
> applications.
We cannot possibly redesign hash functions for everyone's
message space. A random function works well since it is
a random function on any message space.
> It still appears to me that if there are /any/ limits placed on
> the size of the possible messages, a random function will
> deviate from the ideal.
What ideal? Despite what you say you are trying to do, you
have not precisely stated it.
Consider the set of all hash functions for which each
message shorter than 1KB has the same number of 160-bit
digests. Then suppose we choose a function uniformly from
this set. How do we expect it to behave on messages shorter
than 900 bytes? Would the graph you named look more like
that of a random function, or more like the flat line you
seek? How close is it to one or the other?
Note how well the random function model works. If our hash
is a random function when applied to messages of less than
1000 bytes, then it is also a random function when we
restict the domain to messages of less than 900 bytes.
When designing a hash function, resistance to exhaustive
search is a trivial problem. Set the digest large enough
and check off that requirement. The random function model
works well largely because it does not force us into rigid
limited structures that an analyst could use against it.
We'd be foolish to buy neglible additional protection from
exhaustive search by choosing functions from a tiny
stuctured subset where we can't even find candidates that
appear to be anywhere near as strong.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: CLSV <[EMAIL PROTECTED]>
Subject: Re: MIRDEK: more fun with playing cards.
Date: Wed, 19 Jan 2000 16:32:34 +0000
Paul Crowley wrote:
[...]
> Mirdek is IMHO considerably more practical than Solitaire. As you'll
> see from the website, I've spent quite a bit of time with a stopwatch
> and a pack of cards, making sure I've got a cipher that can be done in
> reasonable time. I've successfully decrypted thirty character
> ciphertexts with six character keyphrases in just over twenty minutes,
> using only a conversion chart (which is easily drawn from memory) and
> a pack of cards. Once you've tried doing RC4 by hand and got bored,
> try doing Mirdek, and I think you'll appreciate why I felt the need to
> design a new cipher.
I'm going to check your cipher out when I have more time.
I agree with you that it is better to design a hand cipher
using operations that can be done by hand quickly than
trying to patch a cipher like RC4.
Regards,
CLSV
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: New Crypto Regulations
Date: 19 Jan 2000 17:03:05 GMT
"Douglas A. Gwyn" [EMAIL PROTECTED] writes:
>JPeschel wrote:
>> "Douglas A. Gwyn" [EMAIL PROTECTED] writes:
>> >To the extent that people think a democracy is desirable,
>> >the US ideal of government that promotes individual rights
>> >has already died.
>> This is, of course, pessimistic nonsense.
>
>No, it isn't. A democracy is merely a slowed-down version of mob rule.
>Mobs aren't known for watching out for individual rights.
Wrong again.
Not only was your last assertion wrongheaded,
this latest bit of sophistry, despite
possessing a minutiae of merit as nihilistic
black humor, is elitist nonsense.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Kryptos... Did they finish it?
Date: Wed, 19 Jan 2000 17:10:45 +0000
Heath Smith wrote:
>
> Has David Stein or Jim Gillogy finished the remainder of Kryptos?
I can't speak for Stein, but Gillogly hasn't finished it... yet.
--
Jim Gillogly
Sterday, 28 Afteryule S.R. 2000, 17:10
12.19.6.15.18, 1 Edznab 6 Muan, Third Lord of Night
------------------------------
From: [EMAIL PROTECTED]
Subject: Simple cipher to break for newbies
Date: 19 Jan 2000 17:14:01 GMT
Hi,
I made a simple product cipher-like algorithm so that I could learn a bit
about how these things work, and also so I could try and break it.
I have posted it here for other newbies like me who might like something
simple to poke at. I made a basic round very simple, and put rounds together
in a minimalist (and symmetrical) way. I'm sure it's very weak, as I've only
read one text on cryptography, and only have a fuzzy idea of the attacks
possible.
This 128-bit block cipher uses XOR and S table lookups only. Data are
grouped and processed much as one would do in a Walsh transform, or a FFT.
The obfuscation in this algorithm is provided by a 256 byte S table
generated from the key. I'll represent the x element of S as S(x).
Here is how it works:
A ROUND
In an attempt at a mathematical representation:
A round takes two bytes input (AB) to two bytes of output (XY)
X(A,B) = A ^ S(B) ^ S(B ^ S(A ^ S(B)))
Y(A,B) = B ^ S(A ^ S(B))
This can be implemented as follows:
X = A ^ S(B)
Y = B
then
Y = Y ^ S(X)
then
X = X ^ S(Y)
I mention this, because this is how I first thought of it. I originally
thought of the first two steps of this running in parallel as a sort of one
way hash function. ie. In step two, don't use the result of step one, use
the original data. This is irreversible, as far as I can see. I then
realised that splitting it into two steps makes it reversible. This gives a
function that encodes a byte as a function of itself and the byte next to
it.
I added the third step because my diffusion method goes from left to right,
and I needed something to spread changes in the opposite direction. Also,
it's easy to reverse a single round of two stages if you know the input
plaintext. At the second stage, knowing A would mean you get S(B), and if
you knew the plaintext, you would know A and B.
Having the third operation is also more symmetrical (it simplifies to a swap
for an S table S(x) = x). This is probably bad for a cipher, but nice to
play with.
This round function has the effect of taking in 16 bits of data, and using
an 8 bit table to generate another 16 bits. So anyone with a 16 bit lookup
table could fill it in to have the same effect. I decided I needed to expand
this so that it took more input bits to more output bits. My solution was to
use the two-in two-out round in an FFT butterfly structure to double the
size of a block affected per round by a bit.
HOW ROUNDS ARE COMBINED
Bytes in a block are processed in the following order:
(0 - leftmost byte)
We start with 16 individual bytes:
0 1 2 3 4 5 6 7 8 9 A B C D E F
We group them and process them.
01 23 45 67 89 AB CD EF
Now we have 8 16-bit values which we process again, to give:
0213 4657 8A9B CEDF
Now we have 4 32-bit values.
04261537 8CAE9DBF
And then 2 64-bit,
084C2A6E195D3B7F
and finally we have our 128-bit output.
OBSERVATIONS
With an identity S table (S(x) = x), the round function simply swaps two
bytes. ie. X(A,B) = B, Y(A,B) = A. All the rounds then add up to reverse
your input string for you. :-)
S tables with cycles in them damage the data far less than you would think.
Because the same table is used so much, cycles can result in data bytes
being XORed with close copies of themselves. Very random S tables produce
wonderful-looking "random" output. I haven't tested the output yet.
This algorithm applies the same transformation at several scales, which
implies some form of fractal symmetry in the output. I have been able to
produce picures of Sierpinsky carpets and similar patterns by feeding
different input tables into (modified versions of) this algorithm, and by
using a very ordered S table. I don't know enough about non-linear maths to
see how I would exploit this.
This algorithm looks so similar to a Walsh transform or similar O(n log n)
signal processing function that I am nervous that I am just doing some sort
of linear transform (S table notwithstanding) that leaks information like a
sieve - or perhaps a non-linear transform that does the same. :-)
That all being said I like the algorithm cos I can look at it and see things
I'd like to try to break it, which is more than I can say for DES.
Well, I hope someone else has as much fun with this as I think I will. If
anyone does post or mail any attacks, please warn with a spoiler alert
first.
Good luck,
Ray
=======8<========8<========
/*
* Ray's probably really awful encryption thingum
*
* Don't even use it for your cookie recipies! This is the simplest
* encryption method I could think of that might be close to useful. I
* wanted something simple to pick apart and learn by picking at. This is
* NOT A REAL ENCRYPTION ALGORITHM. It has all sorts of symmetries I want to
* try and exploit.
*
* DISCLAIMER: I am a bored student, not a crypto expert. Don't come crying
* to me if this code somehow gets you into trouble, or causes the same.
*
* Copyright (c) January 2000 Ray Heasman
*/
#include <stdio.h>
#include <stdlib.h>
#define uchar unsigned char
uchar STab[256]; // The "S" table is the permutation table
typedef uchar TBlock[16]; // The basic unit this algo. works upon
void enc(TBlock In, TBlock *Out)
// Encode plaintext block into ciphertext
// Takes 128 bits in, gives 128 bits out
// Applies lookup and XOR to A then B then A again
{
int a,b, step, i;
memcpy(*Out, In, sizeof(TBlock));
step = 1;
while (step < 16) {
a=0; b=step;
while (b <= 16) {
for (i=0; i<step; i ++) {
(*Out)[a] = (*Out)[a] ^ STab[(int) (*Out)[b]];
(*Out)[b] = (*Out)[b] ^ STab[(int) (*Out)[a]];
(*Out)[a] = (*Out)[a] ^ STab[(int) (*Out)[b]];
a ++; b++;
}
a += step; b += step;
}
step <<= 1;
}
a=0; b=8;
}
void dec(TBlock In, TBlock *Out)
// Exact inverse of "enc", provided that the S table is identical
{
int a,b, step, i;
memcpy(*Out, In, sizeof(TBlock));
a=0; b=8;
step = 8;
while (step > 0) {
a=15-step; b=15;
while (a >= 0) {
for (i=0; i<step; i ++) {
(*Out)[a] = (*Out)[a] ^ STab[(int) (*Out)[b]];
(*Out)[b] = (*Out)[b] ^ STab[(int) (*Out)[a]];
(*Out)[a] = (*Out)[a] ^ STab[(int) (*Out)[b]];
a --; b--;
}
a -= step; b -= step;
}
step >>= 1;
}
}
void test(TBlock P)
// Throws a test vector at the encrypter
{
int i;
TBlock C;
TBlock MyP;
enc(P, &C);
// printf("Plain -> Crypt\n");
for (i=0; i<16; i ++)
printf("%02x", P[i]);
printf(" -> ");
for (i=0; i<16; i ++)
printf("%02x", C[i]);
printf("\n");
dec(C, &MyP);
// printf("Crypt -> Plain\n");
for (i=0; i<16; i ++)
printf("%02x", C[i]);
printf(" -> ");
for (i=0; i<16; i ++)
printf("%02x", MyP[i]);
printf("\n");
}
int main(int argc, char *argv[])
// Main thingum. Mostly init stuff.
{
int i,j;
TBlock T;
unsigned char tmp;
// Fill the table
for (i=0; i<256; i++)
STab[i] = (uchar) i;
// Now permute it.
// This is jut to make a sorta random table.. this would be key
// derived in a real cipher.
j = 7;
for (i=0; i<1024; i++) {
if (random() & 1) j = (j + (int) STab[j]) % 256;
else j = (j + (int) STab[i % 256]) % 256;
tmp = STab[i % 256];
STab[i % 256] = STab[j];
STab[j] = tmp;
}
// Print out the S table
printf("Substitution table:\n");
for (i=0; i<256; i++) {
if ((i % 17)==0) printf("\n");
printf("%4d", STab[i]);
}
printf("\n");
// Do some tests
for (i=0; i<16; i++) {
for (j=0; j<16; j++)
T[j] = 0;
if (i < 8)
T[15] = 1 << i;
else
T[14] = 1 << (i-8);
test(T);
};
return(0);
}
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: New Crypto Regulations
Date: Wed, 19 Jan 2000 11:33:53 -0600
In article <86390s$3t8$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Mike McCarty) wrote:
>
> What he meant was, IIUC, that so long as people continue to think that
> democracy is desirable, there is no hope for this country. And I agree.
> This country was founded as a REPUBLIC. We need to stop treating it as
> a democracy, and work to restore the republic.
Surely this is not an either/or decision but preservng and promoting
justice means that there is neither quick mob rule by an emotional
whippedup majority that forgets individual rights of any dissentors, or
suppression of popular dissent about how the selected choose to do things
by, again, denying individual rights.
--
To prevent the comprimise of with the most common configuration
of computers is something like preventing a sculptor from being too original. If a
computer design is corruptable, it will be.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: New Crypto Regulations
Date: Wed, 19 Jan 2000 11:49:10 -0600
In article <863dti$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Guy Macon) wrote:
> In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (wtshaw) wrote:
>...
> >
> >That twist is mere rationalization for doing wrong if used. Justice
> >require using good sense, which is at the root of the situation in the
> >first place.
>
> I disagree with your logic. You are begging the question; if you
> assume that laws such as you propose do not support despots and do
> not hurt the common people who are under their tyranny, then it may
> be "rationalization", but if laws such as you propose do indeed
> support despots and hurt the common people who are under their
> tyranny, then it is you that are guilty of "rationalization". You
> can't assume that an assertion is true and then base your argument
> for the truth of that assertion on the assumption. You need to
> decide what "doing wrong" is first, and I am unconvinced that what
> you propose to punish is indeed "doing wrong".
Justice does not support abuses, from the right, from the left, or from a
unknown or irresponsible party. I figure that that is a pretty good place
to try to stand.
>
> Please note that there are real-world examples of both methods
> available for study. The US has done a fair job of cutting off
> Cuba, while South Korea is taking just the opposite path towards
> North Korea, allowing them as much info and trade as they are
> willing to accept. It is unclear which path is superior.
Cuba is another problem we created, or rather allowed to fester. I for
one tried to do the humanitarian thing at the time of the revolution.
Deaf by habit to dries of mercy, armchair bureaucrats were as usually
clueless as to doing the right thing, fessing up to prior US misconduct;
that failure resulted in driving the local "heros" over there over the
edge. There still is the need of acknowledging sin, now on both sides, if
the best future is to be realized. Brute force justifies nothing,
anywhere, anytime, but it does require brutes.
--
To prevent the comprimise of with the most common configuration
of computers is something like preventing a sculptor from being too original. If a
computer design is corruptable, it will be.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: MIRDEK: more fun with playing cards.
Date: Wed, 19 Jan 2000 17:47:51 GMT
OOPS! You are correct!
That should have been per HOUR.
I am no speed demon.
Rex Stewart
In article <[EMAIL PROTECTED]>,
Paul Crowley <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] writes:
>
> > Actually, I like your idea, and will be trying it out in
> > the next couple of days. As a long time user of cyphers,
> > I have never found a stong hand cypher fast enough to
> > be practical. Solitaire is to slow (IMHO). I cannot seem
> > to get better than about 50 char per minute.
>
> You can't mean you got that speed by hand!
>
> Check out my C implementation of Solitaire on
> http://www.hedonism.demon.co.uk/paul/solitaire/
>
> I don't know quite how fast it goes, but it's rather quicker than 50
> chars per minute.
>
> For that matter, I haven't tested how fast a computer implemtation of
> Mirdek can go. I don't think it matters; one end of the
> communications link will be a hand cipher, and simply can't process
> enough text that the processing at the machine end will take more
than
> a blink of an eye.
> --
> __
> \/ o\ [EMAIL PROTECTED] Got a Linux strategy? \ /
> /\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Java's RSA implimentation
Date: Wed, 19 Jan 2000 17:52:48 GMT
In article <863qd5$sef$[EMAIL PROTECTED]>,
"Artemios G. Voyiatzis" <[EMAIL PROTECTED]> wrote:
> Greeting to all,
>
> Java2 provides the package java.math.BigInteger for big integer
arithmetic.
> In this package there all almost all the routines you may need to
implement
> cryptographic algorithms.
>
> There is a constructor BigInteger(int bitLength, int certainty,
Random rnd)
> which constructs a BigInteger with "bitLength" length in bits and
that is
> probably prime, with probability (1/2)^certainty that is composite.
I would not trust it. Just to cite one reason: there is no probabilistic
method known today whose probability of error after k rounds is 1/2^k.
Thus, there is either an error in implementation or at least an error
in documentation.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
