Cryptography-Digest Digest #275, Volume #12 Sun, 23 Jul 00 23:13:01 EDT
Contents:
Re: 8 bit block ciphers (Bill Unruh)
Re: RC4-- repetition length? (Bill Unruh)
Re: testing an encryption program ("J.P.")
Re: RC4-- repetition length? (Bill Unruh)
Re: PGP US Versions Broken,no good?? (Edward A. Falk)
Re: Proving continued possession of a file (Edward A. Falk)
Re: Proving continued possession of a file (Edward A. Falk)
Re: RC4-- repetition length? (Jim Gillogly)
Re: please take a look at my scheme... ("Scott Fluhrer")
Re: 8 bit block ciphers (Boris Kazak)
Re: testing an encryption program (Jim Gillogly)
Re: Practical application of Ciphersaber (Was: RC4-- repetition length?) ("Trevor L.
Jackson, III")
Hash function? (Boris Kazak)
Can Anyone Recomend A Good Intro Text (Wade Reiber)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: 8 bit block ciphers
Date: 24 Jul 2000 00:10:54 GMT
In <[EMAIL PROTECTED]> [EMAIL PROTECTED] (Mack)
writes:
]That is what I am looking for mathematical or encryption
]methods of producing a 256 byte permutations.
]No shuffling please.
Any permutation can be obtained by "shuffling", so it is unclear what
you want.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: RC4-- repetition length?
Date: 24 Jul 2000 00:16:31 GMT
In <8ldejt$[EMAIL PROTECTED]> [EMAIL PROTECTED] (Guy Macon) writes:
>There are a lot of folks like me who are interested in ciphersaber
>( http://www.ciphersaber.gurus.com ) but are a bity shy of the horsepower
>to tell the good arguments in this thread from the bad. Could one of
>the experts post a practical summary when this discussion is complete?
This thread has nothing to do with ciphersabre. They got involved by
making confusing statements about their implimenation of RC4 or ARC4.
The main topic of this thread was how long the repetition cycles tend to
be in ARC4, and has digressed to how much output you need to tell the
difference (just by looking at the output statistics) between the output
of ARC4 and a truely random sequence.
Read the snake-oil FAQ published here regularly. Look at what they
offer. Ask if their key generation routines are replaceable and open
source. Ask what the exact specification of the output is. Ask for an
exact specificatio of all algorithms used.
------------------------------
From: "J.P." <[EMAIL PROTECTED]>
Subject: Re: testing an encryption program
Date: Mon, 24 Jul 2000 02:19:21 +0200
It's probably something like this:
xxx xxx xxx xx xxxxxxx, xxx xxx xxx xxxxxxx!
who can see the message, bla bla bla decrypt!
Anyway, I don't wanna spend to much time to
decrypting this... It's probably easy for someone with
a lot of time.. Would be easy if you gave us a description
of what kind of data you've encrypted...
I asume a line of text in this case,
If I did get close as far as predicting the word-lengths
your encryption needs some improvement because
someone with some time and programming skills can
just build a tool that speeds up the process of figuring
out what the original words could be and thus your key...
This took only 5 minutes...
Laters,
J.P.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: RC4-- repetition length?
Date: 24 Jul 2000 00:22:27 GMT
In <ukkqsZF9$GA.279@cpmsnbbsa07> "Joseph Ashwood" <[EMAIL PROTECTED]> writes:
>Well to make a potentially long summary quite short:
>1) RC4 is good for a few megabytes of data, but starts
>getting fairly bad around a gigabyte, very bad around 2
>gigabytes, probably breakable around 16 gigabytes.
???? This comes from where? The evidence is that the output is
distinguishable from pure random at about 2GB (just) No way of using
that to break the cypher has been presented. We know all private key
cyphers are not random ( there is a very simply short algorithm which
generates them) Using that fact is the difficulty. So even if we know
rc4 is not exactly random , using that fact is the difficulty.
------------------------------
From: [EMAIL PROTECTED] (Edward A. Falk)
Crossposted-To: alt.security.pgp
Subject: Re: PGP US Versions Broken,no good??
Date: 24 Jul 2000 00:46:54 GMT
In article <[EMAIL PROTECTED]>, jungle <[EMAIL PROTECTED]> wrote:
>see comments inside text ...
>
>>
>> Here are my own comments: I down-loaded an international version
>> of pgp 5 a couple years ago and was unable to even compile it
>> without first fixing a large number of glaring bugs in the source
>> code.
>
>compiler related ?
Utterly, completely broken. There were character
strings that were missing the terminating " character.
The source could not have possibly compiled on *any*
C compiler.
Hold on, let me check my archives. Here it is:
-rw-rw-r-- 1 falk 927363 Apr 7 1999 pgp50i-unix-src.tar.gz
According to the notes I made at the time, the file pgpFullLicense.c
was missing a terminating '\' character on line 74, causing the
license string to not compile. If there was any compiler out there
that could have handled that file, I'd be surprised.
I also had to edit the Makefile and a macro in pass.h.
More importantly, the source file was not signed in any way. The
only reason I didn't just delete the entire source base was that
I occasionally need to decrypt something encrypted with PGP 5.x.
I use 2.6.2 exclusively for my own stuff.
(Not that I have anything against Pgp 5 or Pgp 6, they just don't
run under Unix.)
--
-ed falk, [EMAIL PROTECTED] See *********************#*************#*
http://www.rahul.net/falk/whatToDo.html #**************F******!******!*!!****
and read 12 Simple Things You Can Do ******!***************************#**
to Save the Internet **#******#*********!**WW*W**WW****
------------------------------
From: [EMAIL PROTECTED] (Edward A. Falk)
Subject: Re: Proving continued possession of a file
Date: 24 Jul 2000 00:50:32 GMT
Why can't Alice send a message to Bob that says: Here, concatenate
your copy of the file to this random string and send me the secure
checksum.
Am I missing something?
--
-ed falk, [EMAIL PROTECTED] See *********************#*************#*
http://www.rahul.net/falk/whatToDo.html #**************F******!******!*!!****
and read 12 Simple Things You Can Do ******!***************************#**
to Save the Internet **#******#*********!**WW*W**WW****
------------------------------
From: [EMAIL PROTECTED] (Edward A. Falk)
Subject: Re: Proving continued possession of a file
Date: 24 Jul 2000 00:54:47 GMT
In article <jcKe5.4557$[EMAIL PROTECTED]>,
Kasper Pedersen <[EMAIL PROTECTED]> wrote:
>
>"Samuel Paik" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> I don't understand why you don't just have Alice ask Bob to compute
>> cryptographic hashes of random segments of the file.
>
>I thought of it too, but to me it seemed like he wanted A to check B without
>A still having the file.
You mean Alice had the file, then discarded it and now wants to see if Bob
still has it?
The only solution I see is for alice to compute hash(random+file)
in advance before discarding the file. She'll need to generate as
many of these hashes in advance for as many times as she anticipates
challenging Bob.
--
-ed falk, [EMAIL PROTECTED] See *********************#*************#*
http://www.rahul.net/falk/whatToDo.html #**************F******!******!*!!****
and read 12 Simple Things You Can Do ******!***************************#**
to Save the Internet **#******#*********!**WW*W**WW****
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: RC4-- repetition length?
Date: Mon, 24 Jul 2000 01:37:23 +0000
Bill Unruh wrote:
>
> In <8ldejt$[EMAIL PROTECTED]> [EMAIL PROTECTED] (Guy Macon) writes:
>
> >There are a lot of folks like me who are interested in ciphersaber
> >( http://www.ciphersaber.gurus.com ) but are a bity shy of the horsepower
> >to tell the good arguments in this thread from the bad. Could one of
> >the experts post a practical summary when this discussion is complete?
>
> This thread has nothing to do with ciphersabre. They got involved by
> making confusing statements about their implimenation of RC4 or ARC4.
OK, then let's <make> it about Ciphersaber. What confusing statements
do you say have been made about the use of RC4 in Ciphersaber?
> Read the snake-oil FAQ published here regularly. Look at what they
Done that.
> offer. Ask if their key generation routines are replaceable and open
Uh, you write the source yourself. What are you talking about?
> source. Ask what the exact specification of the output is. Ask for an
> exact specificatio of all algorithms used.
It's bog-standard keyed RC4 with a 10-byte IV, and it's detailed on
the web page quoted above with data against which you can check your
implementation.
Are you thinking of some different program, and getting it confused
with Ciphersaber?
--
Jim Gillogly
Trewesday, 1 Wedmath S.R. 2000, 01:32
12.19.7.7.5, 6 Chicchan 8 Xul, First Lord of Night
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: please take a look at my scheme...
Date: Sun, 23 Jul 2000 18:45:15 -0700
J.P. <[EMAIL PROTECTED]> wrote in message
news:P4Le5.2081$63.38913@zonnet-reader-1...
> Hi !
>
> This is the basic idea behind my MEX (Matrix Excryption Xperiment)
> crypto program. I'm just a student who's doing this as a hobby
> and it's my first attempt to something resembling "encryption".
> I'm trying to figure out a way to improve the strenght of this
> scheme (maybe it's just plain weak and unfixable, I can accept that).
> I would like anybody who's interested to take a look at it and
> post his/hers thoughts and comments.
>
> we take a line of text,
> "Hello this is a test."
>
> and we take a 7 char key,
> "abcdefg"
>
> Now, we read the first set of 4 chars from
> the line of text...
> "hell"
>
> we put this in a 2x2 matrix or box whatever you wanna call it.
>
> -----------
> | H | e |
> -----------
> | l | l |
> -----------
>
> so we can read this as ASCII values:
>
> -------------
> | 72 | 101 |
> -------------
> | 108 | 108 |
> -------------
>
> Now we add the,
> 1st and 4th: 072+108=180
> 1st and 3rd: 072+108=180
> 2nd and 4th: 101+108=209
> 2nd and 3rd: 101+108=209
> 2nd and 1st: 101+072=173
> 4th and 3rd: 108+108=216
> 1,2,3 and 4: 072+101+108+108=389
>
> So our messagepart "Hell" is now converted to:
> "180 180 209 209 173 216 389"
>
> Now we take the ASCII values of our key "abcdefg":
> "097 098 099 100 101 102 103"
>
> We add these so our MEX encrypted messagepart becomes:
> "277 278 308 309 274 318 492"
>
> But since we know that it's 7 numbers consisting of
> 3 numbers between 0-9, we can write it to a file as:
> "277278308309274318492"
>
> The next 4 char block of the message is handled just
> like the first block that I've shown above.
Ok, here's how to break this system, with a "ciphertext-only" attack. Guess
the value of a 4 character segment. If the plaintext is probably English, "
the" is a good guess. Do your transform to convert it to 7 numbers.
Subtract those values from the corresponding values in the ciphertext, and
compute the key. Decrypt the file using that key, and so if that looks
plausible/legal (it may be illegal if a plaintext value must be below 0 or
above 255 to work with that key). Keep on attempting guesses until you hit
one that is correct, which will give you the key.
Or, if you can't make any plausible guesses, just go through all 2^32
possibilities on the first block -- you should be able to test all the
possibilities within an hour or so...
>
> Our completly encrypted message will look like this:
> "277278308309274318492312325235248244322466307235319
> 247321239460244310163229248231379329329316316318333
> 551169170151152173154227"
>
> Note1: This is wrapped for readability, in real routine
> it's written to the file without linefeeds or other
> things like that...
>
> Note2: Sure, the message is now more than 5 times bigger
> than the original message, but winzip can reduce that for me :)
>
> Note3: Last block was filed with "Ord('.') and 3 times 0"
> but when we implement this in real life we can fill this up
> with a different value since we don't wanna give up a part
> of our key this easily !
>
> Decrypting goes like this;
> read first 7 numbers from the encrypted file:
> "277278308309274318492"
>
> We know the key, so we subtract and get this:
> "180 180 209 209 173 216 389"
>
> Now it's just trivial to retrieve the original 4 chars
> by just going from 0-255 in the 1st value of the "2x2 box"
> and using something like this:
Ick, the method I snipped is ugly. Using linear algebra, you can do much
better. For example,
f[1] = (x[1]-x[3]+x[5])/2;
f[2] = x[5] - f[1];
f[3] = x[2] - f[1];
f[4] = x[3] - f[1];
>
> So you only get output (by using the and-statement) if
> you've put the correct/original value in 1st place
> or by some strange coincidence wich is unlikely but I
> found that out by trying to bruteforce my test messages.
No, this system of linear equations is determined -- the solution is unique.
> Was to be expected though...
> We repeat this for every block in the file, e voila, there's
> your original message.
>
> So, the weak points that I can find are:
> - the distribution of the key from encryptor to decryptor.
That's a feature of any secret key system -- it's generally assumed that the
user of such a system will somehow take care of key distribution.
> - the filling up of the last block, since you can't say for
> sure that you've got a message that can be devided in parts
> of 4 chars. the last block can be filled with a character
> of your choice, maybe depending on the key... But still
> it's allmost giving away your entire key ! (main problem I guess)
> - If someone knows the method of encryption, a bruteforce
> crack program can easily be build and strenght will only
> depend on the lenght of the key.
It's usually assumed that the attacker knows the method of encryption.
>
> Maybe if I increase the box/matrix size, and thus the key size
> it will be harder to crack...
Actually, this type of approach has several problems:
- It's based on linear equations. Linear equations usually make weak
encryption, they have too many "nice" properties that an attacker can
usually take advantage of.
- Well, as you noticed, there is significant ciphertext expansion, and zip
will not eliminate all of it...
> But then I will first have to solve the problem of the last
> block. Otherwise it doesn't matter how big the key is, it will
> give itself away if anyone know the used method.
>
> Just drop a reply if you see something interesting in this scheme,
> how to fix that last block problem in a good way...
> If it stinks please tell me so !
Ok, it stinks :-)
> Then i'll just drop the experiment
> and spend my time on something more usefull ;)
If you want to learn more about cryptography (whether it'd be useful is a
totally separate question :-), it suggest you do two things:
- Read some books on cryptography. Applied Cryptography by Schneier would
be a good start, the FAQ has several other good books for beginners.
- If you want to play around with ciphers, start by breaking them. Making
them is the wrong place to start, because a beginner would have no idea
whether he's moving in the right direction or not. If you break a cipher,
you know you are doing something right. After reading the book(s) from step
1, you might want to take a look at some simple ciphers.
--
poncho
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: 8 bit block ciphers
Date: Mon, 24 Jul 2000 02:36:52 GMT
Mack wrote:
*****************
> >Seems entirely possible.
> >You just arrange your 32 bytes in a kind of a shift register,
> >initialize it with the key, and arrange a system of taps in
> >order to modify the content of the register while shifting.
> >Then you shift it 8 positions, capture 8 bits and use them as
> >your encryption byte.
> >The positioning of taps and the operations that you perform on
> >the register data will determine the period of this generator.
> >
> >Best wishes BNK
> >
>
> Good idea but is too linear. At least for provable
> long generators. With a 32 byte shift register this will
> duplicate bytes before the complete table. I am looking for
> something that works like an 8-bit block cipher.
>
> Mack
> Remove njunk123 from name to reply by e-mail
====================
Linearity or non-linearity is up to your design.
You can, for example, take the two leftmost bytes from
the register, multiply them into a 16-bit product,
XOR this product back into the original bytes, then
rotate 1 byte to the left. I have a key scheduler design
that works like this.
BTW, if you want the bytes in the stream to be non-
duplicating before you scan the whole 256-element table,
this is a serious weakness in the cipher design.
Think yourself - in any 256-byte block there will be
ALL 256 bytes exactly 1 time each... quite an invitation
to analysis.
Best wishes BNK
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: testing an encryption program
Date: Mon, 24 Jul 2000 02:41:33 +0000
wes goodwin wrote:
>
> 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.
Looks to me like it's a binary polyalphabetic with period 20, which gives
us a grand total of 2.25 periods to work with. If I'm right, that means
it could be handled with running-key methods, which would be tedious but
eventually feasible -- but perhaps more time-consuming than the casual
sci.crypt reader might want to deal with. Considering that a general
encryption algorithm should keep arbitrary-length messages safe, a better
test might be using period 10 instead and giving two or three times as
much ciphertext to work with. If you're convinced that it's a good
algorithm, it should also be secure against a known-plaintext attack:
that is, you could give half of the plaintext without compromising the
other half.
--
Jim Gillogly
Trewesday, 1 Wedmath S.R. 2000, 02:34
12.19.7.7.5, 6 Chicchan 8 Xul, First Lord of Night
------------------------------
Date: Sun, 23 Jul 2000 22:44:07 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Practical application of Ciphersaber (Was: RC4-- repetition length?)
Your special code may be a problem. I'd recommend using each only once. For
example, use a 128-bit prefix for each real message rather than a 64-bit
prefix. The first half of the prefix should distinguish the message from the
surrounding noise, and the second half of the prefix will be the new prefix
value for the next message.
This approach is quite simplistic and it has really bad problems (is
worthless) in the presence of uncorrected channel errors. However, if the
channel's transport mechanism supports error correction this approach will
eliminate the anomalously high frequency of the special prefix code that will
appear when the true data is a appreciable fraction of the channel capacity.
Guy Macon wrote:
> Great info! I hope that you don't mind a few questions.
> I am not a crypto (or math!) expert. I am an embedded
> systems programmer specializing in systems with a processor
> that costs less $1 and a list price in the $20 to $50 range.
> I like ciphersaber because it's easy to program, easy to
> explain during a code review, and I don't have to pay for it.
> I bury my passphrase in an internal layer of a masked IC; a
> surface probe can't find it, but a dedicated attacker with a
> lot of resources can - My crypto strength should be strong
> enough so that digging for that passphrase is cheaper than
> breaking the cipher, but not much better than that.
>
> Joseph Ashwood wrote:
> >
> >Well to make a potentially long summary quite short:
> >
> >1) RC4 is good for a few megabytes of data, but starts
> >getting fairly bad around a gigabyte, very bad around 2
> >gigabytes, probably breakable around 16 gigabytes.
>
> I have one system with a hardware RNG and a dedicated
> communication channel and processor. I set it up so
> that the sender is always encrypting random data (except
> in the case where the random data contains a special 64
> byte code - that get's discarded) and the reciever is
> always decrypting and discarding the random data. Every
> so often, the sender sends a fixed length message which
> starts with the special 64 byte code. At 9600 bps and
> 10 bits to form a byte, those limits above look like a
> problem. Are they a problem in this application?
>
> >2) The average-case repetition length of RC4 is extremely
> >long, the worst-case repetition length is still quite large,
> >the best-case repetition length is nearly astronomical
>
> The 1-16 GB range mentioned above, is that best, average,
> or worst case? Is there a way that I can avoid it by avoiding
> certain week passphrases?
>
> >3) If you're going to use RC4 make sure you throw away the
> >first several outputs
>
> Is this a proplem with ciphersaber as well? I often do a
> preprocessing stage where I add a random number of random
> bytes to the beginning and end of my plaintext before I
> encrypt it. For humans, that's enough, as they can plainly
> see wher the garbaf=ge stops and the message starts. For
> applications where a microprocessor needs the plaintext,
> I use a special 64 byte start of message code that is never
> found in the random data (I strip it out if it shows up).
>
> >4) Designing your own stream cipher is probably a fool's
> >pursuit
>
> Alas, I have to do my own implementation, and on hardware
> with a really strange instruction set. I am using someone
> elses design (ciphersaber-1).
>
> >There may be more things that show up later in the
> >conversation, but that's the basic sumary to now.
>
> I will be following the original thread as well as this one.
>
> Again. thanks for the summary!
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Hash function?
Date: Mon, 24 Jul 2000 02:51:09 GMT
To the judgement of sci.crypt posters and readers...
Here is the proposal for a very simple hash function -
scalable, fast, byte-oriented.
Everything starts with an array of bytes. The size of array
is equal to the size of future hash, and is named _buffer_.
Array is initialized either with user's key, or, barring
that, with consecutive bytes 1,2,3...
There is a _magic_ 16-bit constant called SEED, equal to
0x6A09 hex, which happens to be first 4 hex digits SQRT(2),
less initial 1.
A byte is read from the hashed message (file), XORed into
the 0-th element of _buffer_. Thereafter the 16-bit number,
built from the 0-th and 1-st elements of _buffer_, is
multiplied by SEED, yielding a 32-bit product.
The 4 bytes of the product are XORed into the first 4
elements of _buffer_.
Thereafter _buffer_ is rotated
left 1 byte. (Big-endian architecture assumed).
After the EOF there are 4 more bytes to be hashed - the
length of the file as 32-bit number.
Finally, the buffer undergoes one more full cycle of
multiplications-rotates, in order for the full avalanche
to happen. The final hash is in the _buffer_.
Hash function Pseudocode:
/********************/
// variables
unsigned int32 product;
unsigned int16 SEED = 0x6A09; //first 4 hex digits SQRT(2), less initial
1
unsigned int16 multiplicand,i;
unsigned byte BUFFER[HASHSIZE]; // whatever the HASHSIZE is #defined
unsigned byte temp, prod[4];
// BUFFER initialize
for (0 to HASHSIZE-1)
BUFFER(i) = i+1; // writing in there consecutive numbers.
// Alternatively, BUFFER can be initialized with user's key
// Hashing
//Before EOF
While (temp = (READBYTE(InputFile)) != EndOfFile)
BUFFER[0] = BUFFER[0]^temp; // XORing the new byte
multiplicand = 256*BUFFER[0]+BUFFER[1];
product = multiplicand*SEED;
split _product_ into 4 bytes from prod[0] to prod[3];
XOR prod[] bytes into BUFFER according to indices;
Rotate BUFFER to the left 1 position;
//This implies BUFFER[HASHSIZE-1]=BUFFER[0],
//BUFFER[0]=BUFFER[1], BUFFER[1]=BUFFER[2], etc.
Read new byte; Repeat;
//After EOF
//Optionally, if file length was determined in
//process of reading, the above procedure can be
//repeated 4 more times, hashing in the consecutive
//bytes of file length (32-bit number assumed)
//Thereafter, the final squashing
For (0 to HASHSIZE-1)
multiplicand = 256*BUFFER[0]+BUFFER[1];
product = multiplicand*SEED;
split product into 4 bytes from prod[0] to prod[3];
XOR product bytes into BUFFER according to indices;
Rotate BUFFER to the left 1 position;
//This is the same procedure as above, without
//reading new bytes, repeated for 1 full cycle
//in order to provide full avalanche.
//Final hash is contained in the BUFFER.
*******************************
N.B. In a practical program it is obvious, that instead of
rotating in memory all the content of BUFFER, one can achieve
same result by indexing the process cyclically (mod HASHSIZE).
Any feedback will be appreciated.
Best wishes BNK
------------------------------
From: Wade Reiber <[EMAIL PROTECTED]>
Subject: Can Anyone Recomend A Good Intro Text
Date: Mon, 24 Jul 2000 02:58:31 GMT
I'm looking for a good introductory text on crytography. Any recommendations?
The best one I've seen so far seems to be Bruce Schneier's "Applied Cryptography".
------------------------------
** 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
******************************
