Cryptography-Digest Digest #263, Volume #12 Fri, 21 Jul 00 08:13:01 EDT
Contents:
Re: RC4 free for noncommercial ? (Guy Macon)
Re: RC4 free for noncommercial ? (Guy Macon)
Re: Good free stream cipher ? (Runu Knips)
Re: Good free stream cipher ? (Runu Knips)
Re: RC4-- repetition length? ("Scott Fluhrer")
Encryption program list... (Laurent ANGELI)
Re: A new cipher........ (Tim Tyler)
Miller-Rabin-test (Thomas Nordhaus)
Re: Implementation of PSS-style RSA signing? (Mark Wooding)
Re: On block cipher and automata (Mok-Kong Shen)
Re: strength of encryption (=?iso-8859-1?Q?H=E5vard?= Raddum)
Re: New stream cipher (Mok-Kong Shen)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: RC4 free for noncommercial ?
Date: 21 Jul 2000 01:42:11 EDT
stanislav shalunov wrote:
>
>
>Runu Knips <[EMAIL PROTECTED]> writes:
>
>> My crypto book states that 'RC4 requires a license fee for
>> commercial use'.
>
>The politically correct way to resolve this issue of stolen trade
>secret is to call your function arc4 or arcfour. You can then use it
>in any applications, just don't mention the word "RC4".
May I suggest just "arcfour" in a probably vain attempt to reduce the
fragmentation and bifercation of our technical terms by a small amount?
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: RC4 free for noncommercial ?
Date: 21 Jul 2000 01:44:14 EDT
Bill Unruh wrote:
>and so the usual name given to this free public
>version is ARC4 ( pronounced are-cee-four).
Concerning my previous post: Never mind. Too late now.
------------------------------
Date: Fri, 21 Jul 2000 08:54:17 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Good free stream cipher ?
Paul Koning wrote:
> Runu Knips wrote:
> > Paul Koning wrote:
> > > Runu Knips wrote:
> > > > I'm looking for a good & free stream cipher algorithm.
> > > How about any good block cipher in counter mode, or CFB mode?
> > > Or are you looking for something different for some
> > > reason?
> > Well, acutally I could use that as well, but AFAIK real
> > stream ciphers tend to be faster.
> That sounds right. Then again, how fast does it have to be?
Actually, I started this thread when I recognized that
Vim (www.vim.org) uses the pkzip encryption which isn't
secure. So I simply wanted to replace that one with
something secure - a minor patch, I thought :).
But unfortunately its far worse. They use a stream cipher
without an initialization vector. Now if that isn't crap,
what else is ??? (I know - using plain xor)
Btw, I've no clue where to put the initialization vector
in the pkzip encryption anyway - it has space for only
96 bits, enough for a reasonable keyword, but not enough
for an IV.
------------------------------
Date: Fri, 21 Jul 2000 09:02:12 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Good free stream cipher ?
Scott Fluhrer wrote:
> Boris Kazak <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Runu Knips wrote:
> > > Scott Fluhrer wrote:
> > > > Boris Kazak <[EMAIL PROTECTED]> wrote in message
> > > > news:[EMAIL PROTECTED]...
> > > > > Runu Knips wrote:
> > > > > > I'm looking for a good & free stream cipher algorithm.
> > > > > > Does anybody have a suggestion ?
> > > > >
> > > > > Recipe: Take BLOWFISH and run the key setup procedure.
> > > > > You will have 5 arrays of subkeys.
> > > > > P[72], S0[1024], S1[1024], S2[1024], S3[1024]
> > > > > Now your stream cipher will look like following:
> > > > > Ct[i] = Pt[i]^P[i%71]^S0[i%1019]^S1[i%1021]^S2[i%1023]^S3[i%1024]
> > > > > (you can verify yourself that 71, 1019, 1021, 1023 and 1024 are
> > > > > all mutually prime)
> > > > > The period of this generator will be equal to the product of
> > > > > all 5 numbers = 77380915780608 ~ 2^46.
> > > >
> > > > And this can be broken (that is, you can reconstruct the array
> > > > contents that the stream cipher uses) with 71+1019+1021+1023+1024
> > > > = 4158 known stream cipher outputs, by Gaussian elimination.
> > >
> > > Funny, I thought about a concept which used mutually prime sized
> > > arrays at home. Using a avalanche addition and extracting the
> > > bits piece by piece using the parity() function should lead to a
> > > good stream cipher, doesn't it ? However, I fear its pretty slow.
> >
> > Gaussian elimination can be defeated by interleaving XOR and
> > addition mod 2^8 in the mixing routine, like this:
> >
> > Ct[i] = Pt[i]^P[i%71]+S0[i%1019]^S1[i%1021]+S2[i%1023]^S3[i%1024]
> >
> > then linear comination of stream bytes should provide no information
> > useful for reconstruction. BTW, I do not think that 5 table lookups
> > and 4 single-clock arithmetic operations are very slow.
What is going on with my newsserver ? My answer to this posting here
doesn't appear, and the above posting doesn't appear either... sci.crypt
is a really small group, shouldn't be hard to load ???
> That doesn't really make Gaussian elimination any more difficult. XOR and
> addition mod 2^8 are the same operation when you look at them mod 2 (that
> is, looking only at the lsbits). So, you can, with 4158 known keystream
> outputs, solve for the LSBits of all the array contents. Once you have
> those, you know the carries into the 2nd LSBit, so you can solve for those,
> and work your way up until you have all the bits.
If my posting was invisible to the others, too, here is the algorithm
I meant originally (had changed that concept completely since then):
=======================================================================
#define X_SIZE 47
#define Y_SIZE 37
#define Z_SIZE 43
struct keysched {
uint32 xv[X_SIZE];
uint32 yv[Y_SIZE];
uint32 zv[Z_SIZE];
uint32 xc, yc, zc;
};
char next_crypt (struct keysched *k)
{
int i, ch;
uint32 x, y, z;
const uint32 C = 0x9e3779b9;
/* loop for all bits of the result */
for (ch = i = 0; i != 8; ++i) {
/* do an avalanche addition on the 3 vectors xv, yv and zv */
x = k->xv[k->xc] += k->xv[(k->xc+3) % X_SIZE] + C
+ rotl (k->xv[(k->xc+13) % X_SIZE], 3)
+ ...
+ rotl (k->xv[(k->xc + X_SIZE-2) % X_SIZE], 1);
k->xc = (k->xc + 1) % X_SIZE;
y = k->yv[k->yc] += k->yv[(k->yc+5) % Y_SIZE] + C
+ rotl (k->yv[(k->yc+11) % Y_SIZE], 3)
+ ...
+ rotl (k->yv[(k->yc + Y_SIZE - 3) % Y_SIZE], 1);
k->yc = (k->yc + 1) % Y_SIZE;
z = k->zv[k->zc] += k->zv[(k->zc+7) % Z_SIZE] + C
+ rotl (k->zv[(k->zc+13) % Z_SIZE], 2)
+ ...
+ rotl (k->zv[(k->zc + Z_SIZE - 2) % Z_SIZE], 1);
k->zc = (k->zc + 1) % Z_SIZE;
/* compute the parity of x,y,z concatenated */
x = x ^ y ^ z;
x ^= x >> 16; x ^= x >> 8; x ^= x >> 4; x ^= x >> 2; x ^= x >> 1;
/* that parity is the next bit for the result */
ch |= (x & 1) << i;
}
return ch;
}
=======================================================================
Thats really slow.
Instead of using a loop and calculating the parity, using a sbox
is far more efficient. And multiple arrays have no real benefit
when using an avalanche anyway.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: RC4-- repetition length?
Date: Fri, 21 Jul 2000 00:00:41 -0700
Bill Unruh <[EMAIL PROTECTED]> wrote in message
news:8l8hfu$g03$[EMAIL PROTECTED]...
> In <8l8a47$dhd$[EMAIL PROTECTED]> "Scott Fluhrer"
<[EMAIL PROTECTED]> writes:
>
>
> ]<[EMAIL PROTECTED]> wrote in message
> ]news:8l80qe$bst$[EMAIL PROTECTED]...
> ]> In article <8l32co$q9t$[EMAIL PROTECTED]>,
> ]> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote:
> ]> >
> ]> > - It is now known that RC4 is efficiently distinguishable from random
> ]> data
> ]> > after 2Gb.
> ]>
> ]> How? The best I was able to do was 2^^31 calls (2^^39 values), which
> ]> found gaps of length 3 (abca) were .00005 too likely and gaps of length
> ]> 4 (abcda) were .00008 too unlikely.
>
> ]Look at digraph statistics. Certain digraphs, such as the (00,00)
digraph,
> ]occur more frequently than expected. Other digraphs, such as the (FF,FF)
> ]digraph, occur less frequently than expected. In addition, if the
attacker
> ]keeps track of the value of i, other digraphs come into play. For
example,
> ]the (i+1,FF) digraph is more likely than expected, and the (00,i+1)
digraph
> ]is less likely. By taking advantage of all these digraph variances (an
> ]exhaustive list appears in the paper), it turns out that 2**30.6 outputs
is
> ]sufficient for a 90% certainty rate.
>
> I have difficulty in understanding this. What differentiates 00 from ff.
> Ie, the algorithm is symmetric under interchange of any two numbers,
> since all arithmetic is modulo arithmetic ( mod ff). This may be true
> for some particular key, but how could it be true of a random key?
Actually, no, the algorithm is not symmetric. For example, in one of the
steps, j is advanced by the permutation element pointed to by i. If that
element happens to be zero, then j is unchanged. If you interchange that
zero with any other value, j is changed. Or, in other words, the algorithm
acts differently depending on the precise value of a permutation element.
Here is a more extended example: suppose we happened to happen apon a state
where, for some N (and S is the permutation array),
i = N-1
j = N+2
S[N] = FF
S[N+1] = N+1
Then, if you do the next-state function twice, that is:
- Increment i by 1, new value = N
- Increment j by S[i]=FF, new value = N+1
- Swap S[i] and S[j], so S[N]=N+1, S[N+1]=FF
- Output S[S[i]+S[j]] = S[N] = N+1
- Increment i by 1, new value = N+1
- Increment j by S[i]=FF, new value = N
- Swap S[i] and S[j], so S[N]=FF, S[N+1]=N+1
- Output S[S[i]+S[j]] = S[N] = FF
That is, the above situation outputs the digraph (N+1, FF) independent of
any other state within the permutation.
Note that this mechanism doesn't work if you replace the value FF with
anything else. In addition, if i=N-1 (which the attacker can know), the
above starting situation happens (assuming a random state otherwise)
approximately 2**-24 of the time. That, coupled with the fact that the
(N+1,FF) digraph happens 2**-16 through normal mechanisms, leads to that
particular digraph being slightly more probable than in a truly random
keystream.
--
poncho
------------------------------
From: Laurent ANGELI <[EMAIL PROTECTED]>
Subject: Encryption program list...
Date: Fri, 21 Jul 2000 10:37:01 +0200
Hi there,
I am looking for the names of generally used programs to encrypt infos
in email, or info on disk
So, if you crypt, what program do you use ?
Thanks in advance
Laurent
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: A new cipher........
Reply-To: [EMAIL PROTECTED]
Date: Fri, 21 Jul 2000 08:31:56 GMT
Simon Johnson <[EMAIL PROTECTED]> wrote:
: [...] third... the end user cannot use an existing algorithm [...]
Why not?
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ UART what UEAT.
------------------------------
From: Thomas Nordhaus <[EMAIL PROTECTED]>
Crossposted-To: sci.math.num-analysis,sci.math
Subject: Miller-Rabin-test
Date: Fri, 21 Jul 2000 10:48:16 +0200
Hi,
if the Miller-Rabin test shows that an odd number N is a b_i-probable
prime for k "randomly chosen" numbers b_i, 1 < b_i < N then the
probability that N is NOT prime can be bounded by (1/4) ^(-k).
This fact is well known.
On the other hand: "Most" base-2 probable primes are prime, and also
"most" base-3 probable primes are prime (I guess). Therefore my question
is:
Do there exist estimates that measure the probability, that a number is
NOT prime, given that it is b-probable prime, depending on b? What about
"independence". Do these probabilities multiply?
Thankful for any helps and hints,
Thomas Nordhaus
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Implementation of PSS-style RSA signing?
Date: 21 Jul 2000 09:00:58 GMT
Thomas Wu <[EMAIL PROTECTED]> wrote:
> I've noticed that PKCS#1 v2.1d1 places the salt at the beginning of
> the hash inputs, while IEEE P1363a places them at the end. Is there
> any advantage to either ordering? Is there any consensus on which
> draft will change to match the other?
Applying the salt at the beginning of the hash effectively randomizes
the hash chaining variable state, making collisions harder to find.
On the other hand, implementing this is a total pain in the neck,
because you have to partially decode the signature data to know the salt
which you need before you start hashing. You can fix this by writing
the salt separately to the beginning of the data (i.e., salt || data ||
RSA(PSS(salt, H(salt || data)))) but that seems horribly ugly.
Putting the salt on the end allows ordinary collisions in the hash
function to be signature collisions, but makes actually processing the
signature much simpler.
I've not implemented the P1363 version of PSS. It seems like a
sufficient improvement over the PKCS#1 version, from a usability point
of view, that adding it is worthwhile. It's not as if it's a great deal
of code, after all.
-- [mdw]
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On block cipher and automata
Date: Fri, 21 Jul 2000 11:49:03 +0200
Terry Ritter wrote:
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
>
> >A common block cipher is a function that, determined by its
> >key, is a (fixed) bijective mapping between its input plaintext
> >and its output ciphertext. It can thus be considered to be
> >a Mealy automaton (or equivalent) with one single state.
> >
> >It seems to be reasonable to expect that a more general cipher,
> >presumably more flexible and thus better in a position to
> >acquire strength, would behave like a Mealy automaton with more
> >than one state and perhaps even provided with some additional
> >subtleties in its state transitions.
> >
> >I suppose that possibly all existing ciphers could be interpreted
> >as very special instances of this general concept which, therefore,
> >should be at the foundation of future crypto designs.
>
> An alternate generalization occurs by expanding the input block size
> beyond the plaintext to also include "extra data." The "extra data"
> can be "state" information, which might depend upon prior cipherings.
>
> The model thus supports conventional block ciphering as a special case
> of "extra data," either as a constant, or as the key. More generally,
> multiple different encryptions (homophones) of the same data can be
> produced, depending upon the value of the "extra data." One way to
> interpret the "extra data" might be as a sort of sub-cipher selection
> value. This ability to dynamically change the cipherings for the same
> data would also seem to be at the essence of a stream cipher.
>
> But when the ciphertext has equal size to the input (including "extra
> data"), the model is operating within the general context of a block
> cipher, yet can now address state, homophonic, and error-detection /
> authentication issues within the cipher proper. By using really
> random values, different blocks can have different "extra data," and
> thus we get different encodings for the exact same plaintext out of an
> ordinary block cipher. By using the same RNG sequence on both ends, a
> masquerading block -- or just a data error -- can be detected by
> finding an incorrect "extra data" value when deciphering. Or the
> "extra data" can represent a "channel number" to support multiple
> real-time conversations within the same ciphering context. Various
> "extra data" uses may occur simultaneously.
>
> In practice, the use of "extra data" implies some data expansion, and
> adding significant extra data to each block means we need a large
> block for best efficiency. But since we always need error-detection
> anyway, and now can handle error-detection as a part of the cipher,
> the overhead may be less than it may at first appear.
Thanks for your comments.
If I understand correctly, I'll summerize the above by saying that the
state can be a function of the plaintext (in the general case all prior
blocks) and of random numbers. If we use physical random numbers
(including online prompt of arbitrary input from the user) these need
to be output (preferably in scrambled form) to the ciphertext stream
so that the receiver can use them to get the same state as the sender
in order to be able to decrypt. In other words, there will be some data
expansion. This expansion may however be justifiable under appropriate
circumstances. On the other hand, if we use a PRNG, then only a secret
seed is needed and the ciphertext can be of the same length as the
plaintext.
The dependence of the transitions on all the prior plaintext blocks
means in my humble view that we are not simply having a Mealy
automaton but in addition employing memory to make decisions, i.e.
we have conceptually something akin to a push-down automaton.
A simple form of implementation is to use a PRNG to direct the
processing of a block, i.e. determining the substitutions/permutations
in it and use some value derived during that computation as feed-back
to influence the PRNG output. The result is then a block encryption
that dynamically changes, not simply in a deterministic way (which
would the case if there were no feed-back to the PRNG) but is
in a way dependent on the plaintext (I'll roughly call that context
dependency).
M. K. Shen
------------------------------
From: =?iso-8859-1?Q?H=E5vard?= Raddum <[EMAIL PROTECTED]>
Subject: Re: strength of encryption
Date: Fri, 21 Jul 2000 11:44:19 +0200
wes goodwin wrote:
> Thank all of your for your help. I am decently confident that my program is
> strong.
> The program is a command line based program, and it can take a 'key' from 1 to 20
>
> printable characters. The program then works on each byte of a specified file--
> It averages the total deciamal value of the 'key' . It then uses the C ^ and
> operator in conjuntion
> with the current byte in the key that the user typed. It works it's way through
> that key, reseting when
> at the end to create another character via the += operator. The file size stays
> the same. The program works exactly
> backwards to decrypt.
>
> There is a 4.269146211e-40 probability or brute force(guessing) the key.
>
> To make a cracking program, you would have to deal with a large number of
> possibilities also.
> Considering the key can be any printable character, and there are 93 on my
> keyboard, and considering
> that you must have the right combination in *order*.There are 1.063664e20
> possible combinations.
> You may or may not have to try that many times.
>
Why don't you present a detailed description of the whole algorithm, and let the
sci.crypt readers try to crack it?
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: New stream cipher
Date: Fri, 21 Jul 2000 14:15:03 +0200
[EMAIL PROTECTED] wrote:
> Description.
>
> Idea of this algorithm goes up to Vigenere cipher.
> Plain text stream is a sequence of bytes.
> Key has length 256 byte. The key is used to generate
> infinite byte sequence of key stream using finite group
> of the order 65536.
> Vigenere Tableau is implemented as multiplication table
> of finite group of the order 256.
>
> Encryption.
>
> Byte of input plain stream and byte of key stream are
> operands of group law of composition.
> This gives one byte of output cipher stream.
>
> Decryption.
>
> Byte of input cipher stream and inverse to byte of
> key stream are operands of group law of composition.
> This gives one byte of output plain stream.
Do I understand correctly that you build up a substitution table of
256*256 to transform the plaintext bytes according to group
multiplication (the entries are product of row and column entries).
So a plaintext character is used as the row entry and a key character
is used as the column entry and the ciphertext character is the
matrix entry. Questions:
(1) Which group of order 256 do you use? Would it be better/worse
to have in the table instead columns that are random permutations?
(2) Which group of order 65536 do you use? How do you generate
the key stream? Does this key stream depend on its turn on a
specific secret key agreed upon by the communication partners?
How? This key stream must have a finite period. How large is that?
Could you say something about the predictability/unpredictability
of the key stream? (You are having a particular PRNG here, right?)
M. K. Shen
------------------------------
** 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
******************************
