Cryptography-Digest Digest #261, Volume #12 Thu, 20 Jul 00 20:13:01 EDT
Contents:
Re: Implementation of PSS-style RSA signing? (Thomas Wu)
Re: strength of encryption (Jerry Coffin)
Block Cypher ("Martin 'SirDystic' Wolters")
Re: Implementation of PSS-style RSA signing? ("Joseph Ashwood")
Re: Idea? Need Comments... (Andru Luvisi)
Re: microwave cd (Paul Rubin)
Re: Idea? Need Comments... (John Myre)
Re: Idea? Need Comments... (John Myre)
Re: Idea? Need Comments... (John Myre)
Re: FWZ1 (David A. Wagner)
Re: Block Cypher ("Joseph Ashwood")
Re: RC4-- repetition length? ([EMAIL PROTECTED])
testing an encryption program (wes goodwin)
Re: FWZ1 (David A. Wagner)
----------------------------------------------------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: Implementation of PSS-style RSA signing?
Date: 20 Jul 2000 15:28:12 -0700
[EMAIL PROTECTED] (Mark Wooding) writes:
> Thomas Wu <[EMAIL PROTECTED]> wrote:
> >
> > Are there any free crypto libraries out there with an implementation
> > of PSS encoding for RSA signatures? PKCS#1 v2.1 refers to the
> > technique as "RSASSA-PSS", and the latest IEEE P1363a draft calls the
> > encoding method "EMSA3", but the two standards seem to differ
> > slightly, for example, in the ordering of hash inputs. What's a good
> > place to look if I want to generate standard-looking signatures of
> > this form?
>
> I've just finished implementing PSS as defined in PKCS#1 v2.1 draft 1 in
> Catacomb, so that'll be available in the next (pre-)release, in a week
> or so's time. It's a pain in the neck to use, because you have to know
> the salt value before you can start hashing the data.
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?
> It uses basically the same operations as OAEP, which I've verified
> against the RIPEMD-160 test vectors. I don't have any PSS test vectors,
> however. If anyone has some (preferably without the actual RSA signing
> step, and based on MGF1 with SHA1, RIPEMD160, MD5 or Tiger), could they
> let me know?
Likewise...
> [Catacomb is free software: you can modify and/or redistribute it under
> the GNU Library General Public License. The current version, 2.0.0pre6,
> which doesn't yet include the PSS support, is available from my personal
> webpages, at http://www.excessus.demon.co.uk/misc-hacks/#catacomb.]
>
> -- [mdw]
--
Tom Wu * finger -l [EMAIL PROTECTED] for PGP key *
E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in
Phone: (650) 723-1565 exchange for security deserve neither."
http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: strength of encryption
Date: Wed, 19 Jul 2000 16:36:07 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> 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.
Unless you're doing a LOT more than you've described above, your
confidence is almost certainly misplaced. From what you've described
above, your algorithm sounds _very_ weak -- to the point that it
would have been quite easy for WWII cryptanalysts to break it even
without any real help.
If the security of your cipher matters even a little bit, you really
need to stick to implementing algorithms from people who know what
they're doing, or else be prepared to spend the next few years
studying the subject so you'll know what you're doing. As-is, you
know just enough to be extremely dangerous.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: "Martin 'SirDystic' Wolters" <[EMAIL PROTECTED]>
Subject: Block Cypher
Date: Fri, 21 Jul 2000 00:35:23 +0200
Hi,
A few weeks ago, i made a first attempt
to write a block cypher, and I wanted to
ask about its strength. It's a little bit more
complex than the other 'How secure is my
cypher'-cyphers, but I hope I can describe
it though.
First, it takes a 64-Bit key from the user.
Then it does 16 Permutations. Each time
it takes every 2nd Bit to form 16 subkeys
of 32 Bit each.
>From each subkey it takes the first and
the last Bit to form a 64 Bit Masking Key.
After generating the subkeys, it asks the
User to enter a string to be encrypted.
This string is padded with zero bits, until
its length mod 62 is 0. Every 62-Bit Block
gets a parity Bit of its first half on the beginning
and one of the second half on it's end.
Then the encryption starts. The second half
of the block to be processed is XORed with
the subkey n. The block then is turned around,
so that the most significant bit becomes the
least significant bit, and so on. This repeats
16 times, so that the block is XORed with
every subkey.
The Masking Key is Left-Shifted by the number
of the processed Block and is then XORed with
the it.
To decrypt the block, the subkeys are used in
reverse order, and after the decryption is complete,
the parity Bits are checked. If they're correct, the
Plaintext is outputted.
I hope my Algorithm isn't as bad as the others.
Bye,
Martin Wolters
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Implementation of PSS-style RSA signing?
Date: Thu, 20 Jul 2000 15:44:48 -0700
Each has it's own advantages. By placing the random number last the state of
the hash function rests more heavily on the random number generator. OTOH if
somehow an attacker finds a way to compute arbitrary hashs, by limiting them
to valid messages for the final stages could be advantageous. Of course this
is ignoring the fact that the random number is transported inside the
encryption of the signature, making it (assumedly) impossible to change. If
it was me, I'd place the random number on the end of the hash. There should
be no real difference in security between them, but placing it after would
seem to me to increase the security by an ever-so-small amount.
Joe
> 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?
------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Subject: Re: Idea? Need Comments...
Date: 20 Jul 2000 15:37:50 -0700
"Big Boy Barry" <[EMAIL PROTECTED]> writes:
[snip]
> 13 - 17 - 24 - 27 - 23
> M Q X A W
What you have is:
a + b = 13
b + c = 17
c + d = 24
d + e = 27
e + a = 23
Five equations, five variables, a little linear algebra...
In this case, if you add the first, third, and fifth and subtract the
second and fourth, you get:
2a = 16
a = 8
With an even number of letters, your system will have 26 solutions.
Just pick a first letter and solve the rest.
Sorry, I wouldn't recommend using this method,
Andru
--
Andru Luvisi, Programmer/Analyst
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: microwave cd
Date: 20 Jul 2000 22:50:25 GMT
In article <[EMAIL PROTECTED]>,
Steve Rush <[EMAIL PROTECTED]> wrote:
>>Probably the most convenient and effective thing to do, especially if
>>you have a lot of CD's to destroy, is take them to the city dump and
>>toss them into a high temperature incinerator.
>
>Are there any municipal garbage incenerators still operating in the USA? I
>thought the EPA banned them years ago.
I don't know. I was kind of wondering that when I made that post.
The only time I saw one was many years ago. It was impressive. I
could have easily jumped in or thrown someone else in, and no remains
would have ever been found. So I wondered whether municipal
incinerators might have been closed off to the public for liability
reasons. I hadn't really been thinking of the EPA angle.
>Throw something in the garbage now, and it goes into a landfill.
>
>If you have too many CDs to conveniently use a torch, find a place where open
>fires are permitted and build a bonfire.
I had thought that incenerators ran at much higher temperatures than a
bonfire could, and that the effluent was scrubbed, so most of the
pollutants were eliminated that way.
I wouldn't want to actually melt/burn the discs with a torch; just
slag the metal layer that contains the data.
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Idea? Need Comments...
Date: Thu, 20 Jul 2000 16:43:42 -0600
Joseph Ashwood wrote:
> The problem is that the mapping is 1-1 onto, so an
> inverse function exists.
Not unless the function isn't what it seems.
He rotates the password by one letter, then adds. That
means that the sum of the encoded letters is twice the
sum (modulo 26) of the original letters. Since 26 is
even, that means that half of the possible 5-letter strings
are not possible encodings: the sum of the encoded letters
must be even. Therefore the function cannot be (uniquely)
inverted.
You could perhaps look at this as a linear equation problem.
Let the input be (a,b,c,d,e) and the output be (Q,R,S,T,U).
Then
( 1 0 0 0 1 ) ( a ) ( Q )
( 1 1 0 0 0 ) ( b ) ( R )
( 0 1 1 0 0 ) x ( c ) = ( S )
( 0 0 1 1 0 ) ( d ) ( T )
( 0 0 0 1 1 ) ( e ) ( U )
This is solvable, except that at one point you need the
inverse of 2, which doesn't have an inverse modulo 26.
That is, you get something like 2a = X, and there are
two possible values for a then. Everything else is fine.
(If X comes out odd, then there is no possible value for
a, which means (Q,R,S,T,U) is not really the output).
With an even number of letters in the password, it gets
worse. Then the equations are linearly dependant and
you can't solve it at all. Equivalently, every guess for
the first letter works. The value of any one output
letter is determined by the rest of the output letters.
This may be a nice little checksum on the output, but
doesn't help reconstruct the input.
(Try, for example, some two-letter passwords...).
JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Idea? Need Comments...
Date: Thu, 20 Jul 2000 17:10:45 -0600
Andru Luvisi wrote:
<snip>
> 2a = 16
> a = 8
<snip>
Or a = 21.
Then b=18, c=25, d=25, e=2: URYYB (I think).
That is, adding 13 to every letter gives you the
same output.
JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Idea? Need Comments...
Date: Thu, 20 Jul 2000 17:05:27 -0600
John Myre wrote:
<snip>
> ( 1 0 0 0 1 ) ( a ) ( Q )
> ( 1 1 0 0 0 ) ( b ) ( R )
> ( 0 1 1 0 0 ) x ( c ) = ( S )
> ( 0 0 1 1 0 ) ( d ) ( T )
> ( 0 0 0 1 1 ) ( e ) ( U )
<snip>
Oops. I transposed the matrix. The comments still apply.
JM
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: FWZ1
Date: 20 Jul 2000 16:11:45 -0700
Oh, look, it's a cheesy LFSR-based stream cipher!
And almost everything in sight is linear. My first reaction is
that I'll be amazed if this is truly secure, but hey, who knows?
Basically, you take a 96-bit LFSR (that's st1[]). You pull a byte
from it (x1). You use the low 4 bits of x1 as an index to select a
byte (x2') from a 128-bit hunk of state (st2[]). You use the low 4
bits of x2' as an index to select a second byte (x2'') from st2[].
You xor x1, x2', and x2'', and the result is your keystream byte.
Each keystream byte gets xor-ed against the plaintext.
Here's how the state st2[] is updated. It is divided into four 32-bit
words. Each word is the accumulated sum of some word of st1[]. Do note,
at this point, that the low bit of a sum is a linear function of the
summands, so the low bit of each word of st2[] is also a known linear
function of the key. The only non-linearity is the 4-bit lookup.
Did anyone spot any mistakes in the above?
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Block Cypher
Date: Thu, 20 Jul 2000 16:12:58 -0700
Please permit me to attempt to translate this from program to something
approximating an algorithm for those if use that would rather deal with it
that way, after all the mechanics of the program should not impact the
mechanics of the cipher, and vice versa.
Key_Schedule(key)
perform some improperly defined voodoo to form 16 32-bit round
keys(called roundkey[]), and 1 64-bit mask key (called mask)
end Key_schedule
Encrypt(key(64-bits), data(62-bit block), n(block number of data))
call KeySchedule(key)
generate parity of first 31 bits, place at beginning
generate parity of last 31 bits, place at end
data is now in 64-bit blocks (idealogically 2 32-bit subblocks called
block[])
for round = 1 to 16
block[2] = block[2] XOR roundkey[round]
split block[1,2] into 64 bit size entities called bit[]
for x = 1 to 64
bitprime[x] = bit[64-x]
bit = bitprime
block = bit (split bit back into 32-bit entities in block)
end for
mask = mask << n (<< if left shift)
block[1,2] = block[1,2] XOR mask
end Encrypt
Now for some analysis. This is at first glance a very basic feistel
structure. A second look though reveals that it is in fact dealing with a 31
bit block (the parity does nothing for security except providing an attacker
with some idea whether the key was correct), that makes it very cumbersome
to deal with in software. The bit by bit reversal of the block has a similar
effect. The diffusion of the cipher is completely absent, that is to say
that one could perform the exact same operations (barring the parity) on a
bitwise level, making the effective block size not 62-bits as presented but
in fact 1 bit. This aspect of the cipher can certainly be exploited, and
because of this I would expect that one known 62-bit block would probably be
sufficient to determine the key, but that depends on your key schedule. For
a key schedule permutations are far from the strongest primitive, because if
the permuation is fixed then finding one complete state reveals all previous
and future states. The mask apparently does little except provide leverage
for the attacker, especially if 2 identical blocks of data are sent in
sequence, that would allow the attacker to gain all bits of the mask, which
since it's based on permutations, would reveal the entire key. What you
might try doing is building an f(x,y) that takes 2 32-bit entries, by
calling it with block[1] and the round key you can introduce diffusion, and
eliminate the ability to split the block up into 1-bit segments. You should
also investigate using a stronger primitive than permutation for computing
your round functions, try to make it such that the entire state is never
revealed in one subkey, and such that even if the current output is known it
reveals little about any other round key, also try to make it impossible to
run backwards (i.e. given roundkey[i] it is not possible to compute
roundkey[j] for j < i) even given the entire state. And lastly, unless you
can find a way to completely decorrelate thet mask from the other values,
either eliminate it or make it the first operation, where it will server as
a barrier to analysis.
Joe
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RC4-- repetition length?
Date: Thu, 20 Jul 2000 23:09:07 GMT
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.
- Bob Jenkins
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: wes goodwin <[EMAIL PROTECTED]>
Subject: testing an encryption program
Date: Thu, 20 Jul 2000 18:32:13 +0000
hey, don't get me wong. I doubt no one,
but I've heard alot of talk talking about people's encryption being
sorry.
I would like to see some action. I was wondering if anyone can decrypt
this text file.
I would love to see this happen as it was encrypted with my program.
again, don't get me wrong, I never was offended by anyone's comments. I
am not in
the crypto business, so my program doesn't matter at all. I made it for
the fun of it.
www.mindspring.com/~goodwine/text_file.txt
This is a simple one line txt file. I would like to see someone decrypt
it.
thanks, and no offense meant or taken.
wesley
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: FWZ1
Date: 20 Jul 2000 16:34:54 -0700
David A. Wagner <[EMAIL PROTECTED]> wrote:
> Basically, you take a 96-bit LFSR (that's st1[]). You pull a byte
> from it (x1). You use the low 4 bits of x1 as an index to select a
> byte (x2') from a 128-bit hunk of state (st2[]). You use the low 4
> bits of x2' as an index to select a second byte (x2'') from st2[].
> You xor x1, x2', and x2'', and the result is your keystream byte.
Oh, look at that. If x1 = x2' mod 16 (happens with probability 1/16),
then the keystream byte is just x1. The rest of the time, the keystream
byte agrees with x1 with probability 1/256. So, each keystream byte has
a 15/16 * 1/256 + 1/16 = 0.066 probability of disclosing x1.
This is a strong correlation between the keystream output and the LFSR
state, so it can almost certainly be used in a correlation attack to recover
the key material. I won't develop all the theory here to calculate how
much ciphertext is required, though. In any case, this looks like a big
foot in the door for the cryptanalyst.
Alternatively, one can trade off texts for time. Here is an impractical
attack that recovers the key material with high probability with about
2^71.5 work and 182 bytes of known text. This is thoroughly infeasible,
but is simpler to explain than the sophisticated techniques used in
correlation attacks. We expect about 0.066 * 182 = 12 bytes of keystream
which agree with x1. Note that such a set gives 96 bits of information
on the LFSR, which is enough to solve for the LFSR state by using Gaussian
elimination. So, we try all C(182,12) = 182! / (170! 12!) ~ 2^60.7 ways
of choosing 12 distinguished bytes from a set of 182 choices, and for each
one we recover a suggested key value which may be tried on other ciphertexts.
The Gaussian elimination requires 12^3 ~ 2^10.7 simple steps per combination
tried, so the total cost is 2^60.7 * 2^10.7 ~ 2^71.5 steps of computation.
Full correlation attacks will of course be much more effective than the
simplistic trick sketched in the previous paragraph, but this trick does
shows that the cipher has at best a 72-bit effective keylength.
------------------------------
** 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
******************************
