Cryptography-Digest Digest #764, Volume #11 Sat, 13 May 00 06:13:01 EDT
Contents:
Re: PlatyMAC a new Message Authentication Code. (David A. Wagner)
An almost-attack on Pikachu (David A. Wagner)
Re: An almost-attack on Pikachu (David A. Wagner)
Re: Key generation for lja1 (Andru Luvisi)
neural network ("G. R. Bricker")
homophones ("G. R. Bricker")
Re: AES final comment deadline is May 15 (Mok-Kong Shen)
On higher level Feistel schemes (Mok-Kong Shen)
Re: zeroknowledge.com and freedom.net - Snake oil? (Guy Macon)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: PlatyMAC a new Message Authentication Code.
Date: 12 May 2000 21:41:08 -0700
In article <[EMAIL PROTECTED]>,
David Formosa (aka ? the Platypus) <dformosa@[202.7.69.25]> wrote:
> >For instance, consider G_bad defined by G_bad(x) := S(t(x))
> >where S() represents a secure stream cipher (e.g., RC4 or 3DES-OFB)
> >and where t() is the function that drops the high byte of its
> >input. Clearly this G_bad is a secure PRG if S is;
>
> I don't quite aggry with you here, anything that ignores a bit of its
> key is not a secure.
Well, the usual definition of a secure 'pseudorandom generator'
(at least in the theory literature) is a function G : {0,1}^n -> {0,1}^m
with m >> n so that, if you pick k uniformly at random from {0,1}^n,
then no computationally-bounded adversary can distinguish between G(k)
and a bitstring chosen uniformly at random from {0,1}^m.
Such a primitive _is_ allowed to ignore a bit of key material, and
_is not_ guaranteed to be secure when used as G(key xor IV), where
the IV is under adversarial control.
> Rather then useing F which IMHO just adds a new thing that could go
> wrong could the following construct be used?
>
> G(x) := S(x) ^ IV
>
> Where ^ is xor and S(x) is a secure stream cypter?
I believe your MAC will then be insecure. The output of the MAC
is a linear function of the IV and of the message. Thus, I would
expect that linear algebra (e.g., Gaussian elimination) will suffice
to thoroughly break the scheme, with not too many known texts.
Yes, it does seem to be important to use a real pseudorandom
function F. Don't skimp here. (This is not the slow part anyway.)
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: An almost-attack on Pikachu
Date: 12 May 2000 22:21:50 -0700
Here is an almost-attack on Pikachu, which turns out *not* to work on the
real cipher, but which could easily have worked, if not for some good luck
on the part of the cipher design (it seems).
Pikachu's F function xors its input with a key to get (a,b,c,d), applies
a linear mixing layer to receive (2a+b+c+d, 2a+2b+2c+d, a+b+2c+d, 2a+b+2c+2d),
applies four different bijective 8-bit S-boxes, and xors again with another
32 bits of key material, and rotates the result left by one bit.
Note that we have nice differentials such as (128,0,0,0) -> (0,0,128,0)
and (0,0,128,0) -> (128,0,0,0) of probability one for the linear layer.
In this case, only one of the four S-boxes will be active, and avalanche
will be limited. In particular, if we have a differential 128 -> 64 of
probability p for the appropriate S-box, after the one-bit rotation we will
get a F-function output difference of a similar form to the the above.
In particular, we do have the following differential:
(0,0,128,0) -> (128,0,0,0) with probability 1/128 for all of F,
by using the corresponding characteristic for the linear mixing layer
(prob. 1) concatenated with the characteristic 128 -> 64 for S-box 0
(prob. 1/128).
We might naively expect to also get in a similar way a differential
(128,0,0,0) -> (0,0,128,0) for the whole F function. However, in this
case it turns out that we are simply lucky -- the differential 128 -> 64
for S-box 2 has probability exactly zero, by good luck, and so this idea
doesn't work.
However, if the second such differential did work for Pikachu's F function,
we'd get a 3-round iterative differential characteristic of prob. ~ 1/2^14,
like this: (I omit the swaps)
( 0, 0, 0, 0) ( 0, 0,128, 0)
(128, 0, 0, 0) ( 0, 0,128, 0)
(128, 0, 0, 0) ( 0, 0, 0, 0)
(128, 0, 0, 0) ( 0, 0, 0, 0).
The first round of the above has probability 1/128; the third round has
probability one; and the middle round *would* have prob. ~ 1/128, too, if it
weren't for our good luck. Thus, if not for our good luck, there would be
a 10-round differential characteristic with prob. ~ 1/2^42, and by bypassing
the first round and using a 1-R attack, the cipher would probably fall with
something like 2^43 chosen plaintexts. (Right?)
However, none of that works, because of the good luck of the choice of
S-boxes! Nonetheless, it is still discomforting to me that even one such
good 1-round differential exists, that the 3-round iterative differential
*almost* worked out, and that it is possible for the cryptanalyst to control
the linear mixing layer so effectively.
I conclude that Pikachu has some unexpectedly good differentials and some
surprising structural properties. Maybe this should be worrying. Yet, on
the other hand, there does not seem to be any obvious way I can see at the
moment to exploit these structural properties in a full attack on Pikachu,
so an alternate interpretation is that perhaps we should be reassured!
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: An almost-attack on Pikachu
Date: 12 May 2000 22:38:36 -0700
By the way, if the rotate were omitted but the same S-boxes used, there
would be a 3-round iterative differential characteristic of probability
1/2^13, and thus a 10-round char. with prob. 1/2^39, so we'd expect to
break this variant with O(2^40) chosen texts.
Also, we can think about linear characteristics. However, with the plain
Pikachu, doing the analogous thing for linear cryptanalysis doesn't work
in a nice way any more, because the rotate "goes the wrong way". Thus,
the natural linear attack on Pikachu doesn't seem to work.
On the other hand, if we omit the rotate but keep the same S-boxes, we
obtain a 3-round iterative linear characteristic of probability
1/2 + 1/512, and thus a 10-round char. with prob. 1/2 + 1/2^25, so we'd
expect to need O(2^50) known texts to break the variant cipher with this
attack, if all works out as expected.
Also, if we switch the direction of the rotation, there is a linear
attack. We get a 3-round iterative approximation with probability
1/2 + 3/2^12 and thus a 10-round char. with prob. ~ 1/2 + 1/2^27.7,
which suggests that there could be a linear attack on such a variant with
something like O(2^55) known texts.
Still, I can't seem to make this work on the real Pikachu. Any ideas?
------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Subject: Re: Key generation for lja1
Date: 12 May 2000 22:46:40 -0700
[EMAIL PROTECTED] (David A. Wagner) writes:
> Why should we expect that all of the key[] array will be initialized?
> Or, why should we expect that the key[] array will yield a permutation?
> Perhaps I am misreading the code, but it's not clear to me that either
> is guaranteed from the algorithm below. I must be confused.
>
> And, while I'm at it, why does the main loop start at i=254 and not i=255?
> Also, are you expecting that the following algorithm will yield key[]
> arrays that have a cycle of length 256? I don't see why it should.
There are 255! cycles of length 256. To create one, I just started
with some element, in this case 255, and then generated the next one
in the sequence, and the next one after that, and so on, filling in
the key[] array as I went along. The key[] array is not initialized
upon entering the function. I'll try to annotate it to see if I can
make the theory make more sense.
> In article <[EMAIL PROTECTED]>,
> Andru Luvisi <[EMAIL PROTECTED]> wrote:
> >
> > Because the hash function for lja1 is basically an eight bit codebook
> > run in cipher block chaining mode, and long periods are generally
> > considered a good thing in a block cipher, I suspect keys which would
> > have a cycle of length 256 would be stronger than keys with shorter
> > cycles. In an extreme case, if every key[i] = i, then the compression
> > function would not change the accumulator when hashing zero bytes.
> >
> > Here's my attempt at a key generator. Suggestions invited:
> >
> > void make_key(unsigned char *key)
> > {
> > unsigned char numbers[256];
> > unsigned char temp;
> > unsigned int i, j, next;
> > FILE *fp;
> >
> > if((fp = fopen("/dev/urandom", "r")) == NULL)
> > {
> > /* a little harsh, but this is demo code */
> > fprintf(stderr, "Can't open /dev/urandom\n");
> > exit(1);
> > }
> >
> > for(i = 0; i < 256; i++)
> > numbers[i] = i;
The numbers array is where we will be picking the "next" element in
the cycle from. We will be picking and effectively removing each
element as we go, to make sure each time that we are going to an
element that has not been used yet. This is how we make sure that the
entire key[] array is initialized and the cycle is of length 256.
> > next = 255;
255 is my starting place. This is arbitrary. The first element to be
filled in will be element 255, and the last element filled in will
contain 255.
The loop below picks 253 elements, and tacks them onto the end of the
sequence.
> > for(i = 254; i > 0; i--)
> > {
> > fread(&j, sizeof(j), 1, fp);
> > j = j % (i + 1);
These two lines pick a random element from among numbers[0] to
numbers[i].
> > temp = numbers[i];
> > numbers[i] = numbers[j];
> > numbers[j] = temp;
These three lines place the selected element into numbers[i], and
whatever was in numbers[i] go into the slot that was previously
occupied by the selected number.
> > key[next] = numbers[i];
The current "end" of the cycle (meaning the end of what I've filled in
so far) is filled in with the next number in the cycle, the one
selected above.
> > next = numbers[i];
The number selected becomes the index of the new "end". That is, the
next slot in the key[] array to fill in. Hence the name "next".
> > }
> >
> > key[next] = numbers[0];
> > next = numbers[0];
> > key[next] = 255;
These three lines enter the last remaining number into the second to
last slot to be filled, and enter 255 into the last slot, closing the
loop, so to speak.
> >
> > fclose(fp);
> > }
> >
Does it make any more sense now?
Andru
--
==========================================================================
| Andru Luvisi | http://libweb.sonoma.edu/ |
| Programmer/Analyst | Library Resources Online |
| Ruben Salazar Library |-----------------------------------------|
| Sonoma State University | http://www.belleprovence.com/ |
| [EMAIL PROTECTED] | Textile imports from Provence, France |
==========================================================================
------------------------------
From: "G. R. Bricker" <[EMAIL PROTECTED]>
Subject: neural network
Date: Sat, 13 May 2000 06:45:35 GMT
As I understand it, a typical neural network would have x number of inputs
and y number of outputs. The middle layer(s) between input and output are
"trained" so that for all possible inputs, you obtain the desired all
possible outputs. This is analagous to a "key" or known algorithm. I'm
thinking of a backpropagation neural network, although other networks could
be used.
Now, this is off the cuff, so please correct me if I'm wrong. If the
number of possible inputs exceeds the number of possible outputs, then
there would be instances where 2 different inputs could give the same
output. Not desireable for crypto. Conversely, if the number of inputs is
less than the number of possible outputs, then there would be outputs which
do not correspond to any inputs. These could be considered "null" outputs.
This could prove useful in some circumstances, particularly if you wanted
to confound a cryptanalyst. So, let's say that the number of possible
outputs must equal or exceed the number of possible inputs.
Now, the recipient of the encoded message must have exactly the same
neural network in order to decode the message. So far this is almost like
having any other cipher in which both parties must have the same key. No
real advantage to using a neural network yet.
However, the idea which interests me is the possibility of "retraining"
the neural network after each message. Suppose that after I have decoded
the message and read it, I then apply that message to the input of the
neural network and "force" the output to be, for example, all ones (1's).
The sender of the message also does this after sending the message.
If the neural network is carefully designed so that each both the sender
and recipient's networks retrain exactly the same way (no random elements),
then each person would have a new neural network, but they would be
identical. The practicality of this would be that each following message
would be encoded differently. Essentially, it would be similar to each
message creating a new key for the next message. This would be an "evolving
key". Very intriguing...
Now, the neural networks I've seen and programmed would not work for this.
However, I think some clever fellow could come up with something that would
work. Again, I'm thinking of some modified backpropagation network.
So, here's an idea. Create a modified backpropagation network with 256
inputs and 257 outputs. One output will not correspond to any possible
input. Every time you send or receive a message, you retrain your network
with the message as your input and the last non-corresponding output as
your output. This changes the algorithm (key). It also generates a new
non-corresponding output to use for the next message.
The advantage? The cryptanalyst must be able to recreate your neural
network in order to decode your NEXT message unless he/she resorts to using
some sort of brute force attacks.
The disadvantage? If the cryptanalyst succeeds in recreating your neural
network, all future messages (and perhaps all past messages) can be read in
real time.
This means that rather than trying to hide your key, you're trying to hide
or protect your algorithm (initial neural network parameters). This goes
against the advice of most crypto people, who assume that the enemy knows
your algorithm and is merely concerned with finding a specific key.
I'm not denouncing the idea. I'm just saying that it has some pitfalls
which need to be worked out. Since the neural network (algorithm) is
essentially the same as your key, a successful cryptanalyst has everything
he needs to continue reading your messages forever. So, before you try
creating a neural network to encode, you should probably first try to
determine a method to overcome this problem.
Personally, I think your idea has potential. I'm going to stew on it...
G. Bricker
------------------------------
From: "G. R. Bricker" <[EMAIL PROTECTED]>
Subject: homophones
Date: Sat, 13 May 2000 06:58:30 GMT
In Singh's book there are some examples such as what you have discussed.
Try these. If you create digraphs, trigraphs, and tetragraphs you will find
that you can identify some of the letters fairly quickly. That's enough of
a wedge to determine most if not all of the ciphertext. For very short
messages, homophones are as secure as any other code. For long messages (or
many short messages using the same keys), you can begin to identify letters
by :
1) noting how often they are paired with other letters (numbers)
2) noting that they are more prevalent at the beginning, middle, or end of
words.
3) noting that two letters (or numbers) only occur in a specific order
(qu).
And, of course, if you suspect a specific word or words are in the cipher
text (such as "enemy") that is also a wedge. Remember the Brits dropping
mines in the Baltic and North Sea in order to elicit the Germans into using
the grid coordinates and the word "mines"?
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: AES final comment deadline is May 15
Date: Sat, 13 May 2000 11:08:03 +0200
Bryan Olson wrote:
> I tend to disagree. I'm not convinced the mailing lists
> and newsgroups are where the AES action is.
Certainly the proper AES 'action' is done by the authors of the
submissions. However, it could be said that the ensemble of
crypto mailing lists and crypto newsgroups is the proper place
where the general opinions of the crypto community are to be
found, I suppose.
> Sort of. It's destined to be T H E symmetric block cipher
> of the next few decades, and probably T H E symmetric
> cipher. But sci.crypt's obsession with secret key encryption
> is out of touch with both modern cryptology and the
> cryptographic market. AES is not among the "New Directions
> in Cryptography". It's a replacement for DES.
Isn't it that both secret key and public key encryption are needed
in practice? I suppose your 'sci.crypt's obsession' is a bit exaggerated
point of view. It is true that public key schemes are relatively seldom
discussed. On the other hand, anyone of the group, if he likes, can
exercise some influence on the 'atmosphere' of discussions, in
particular
through initiating new threads on new topics of interest.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: On higher level Feistel schemes
Date: Sat, 13 May 2000 11:09:32 +0200
Previously I suggested several possibilities of
variations of a given block cipher, including using
varaible keys, permuting the subkeys and permuting the
S-boxes for different rounds. In all these variations
the block size remains unchanged. In the following
a simple, in fact trivial, possibility of doubling
the block size of a given cipher is indicated.
We note that a Feistel scheme is customarily applied
inside a block cipher, e.g. DES. However, given any
block cipher of size n bits, denoted by the function
E in the following, one can easily build a cipher of
block size 2n bits though defining a typical Feistel
round as follows:
L_(i+1) = R_i
R_(i+1) = L_i xor E(K_i, R_i)
where L_i and R_i each have n bits and the subkeys
K_i are to be obtained through some appropriate
key scheduling.
An apparent disadvantage of this lies of course in
speed. However, the scheme appears otherwise to be
o.k. At least theoretically, one could recursively
apply the Feistel scheme to obtain ciphers of
increasingly larger block size.
Thanks for your critiques and comments in advance.
M. K. Shen
================================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: zeroknowledge.com and freedom.net - Snake oil?
Date: 13 May 2000 05:31:44 EDT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Anton Stiglic) wrote:
>
>"Dr. Yongge Wang" wrote:
>
>> Surely I agree with you that is not a practical attack..
>> which is just the same as the key-escrow system or the
>> threshhold cryptosystem... I have just had a rough look at
>> their whitepage (I have to say that I have no time to look
>> at details, so I may wrong some where)..It seems that
>> there is much for the deployment of the Freenet servers.
>> If all the servers are deployed by ZKS, then indeed you
>> have no privacy. You have to trust ZKS (ZKS can easily
>> trace you). Then the problem is why we need a such complicated
>> system instead of choosing a simple anonymizer proxy like
>> www.anonymizer.com ?
>
>Most of the Freedom servers are owned and are run by
>independent servers, and a user can choose which servers
>he wants to use for his route. You can choose servers from
>the US, Canada, Japan, operated by people you thrust. This is
>a big difference from the Anonymizer system.
>
And, if this isn't enough for you (and you have the resources),
set up your own freedom server!
------------------------------
** 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
******************************
