Cryptography-Digest Digest #274, Volume #12 Sun, 23 Jul 00 20:13:00 EDT
Contents:
Re: Random Appearance (Guy Macon)
Practical application of Ciphersaber (Was: RC4-- repetition length?) (Guy Macon)
Re: Proving continued possession of a file (Samuel Paik)
Re: Proving continued possession of a file ("Kasper Pedersen")
Re: Compression & Encryption in FISHYLAND (Tim Tyler)
please take a look at my scheme... ("J.P.")
Re: 8 bit block ciphers (David A. Wagner)
Re: 8 bit block ciphers (David A. Wagner)
Re: Practical application of Ciphersaber (Was: RC4-- repetition length?) ("Scott
Fluhrer")
Re: Crypto jokes? (potentially OT) (David A. Wagner)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Random Appearance
Date: 23 Jul 2000 15:06:40 EDT
Mack wrote:
>
>
>>Joseph Ashwood wrote:
>>> That's not correct. OTP's are subject to known-plaintext
>>> attacks, ...
>>
>>No, they are not, since the only plaintext that is "recovered"
>>is exactly the plaintext that was already known. The point
>>being that "One-Time Pad" in such a context means the
>>theoretically secure system, not a potentially flawed
>>attempt at implementation of such a system.
>
>The code book systems to which I was refering are exactly
>the same as OTP's. The pad may be reused at the risk of
>a known plaintext attack.
"THE PAD MAY BE REUSED????"
Which part on "One Time" are you having trouble understanding?
>The words for messages are
>compiled into a list each word has a different meaning.
>These pads are usually only a couple of pages and then
>compiled into a book. Different 'chapters' are used depending
>on some information. This system was used during WW2
>if I am not mistaken. Each 'chapter' is an OTP. If a chapter is
>reused it is subject to known-plaintext attack . Of course if the
>OTP is stolen it is also broken. In actual use pads were used
>for a certain time period.
So you have proven that a ONE TIME pad that is used MORE THAN ONCE
is insecure. True but not useful. If I use the strongest crypto
system in the world then append my plaintext and my key to my
ciphertext, then my crypto system is vulnerable. True but not
useful.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Practical application of Ciphersaber (Was: RC4-- repetition length?)
Date: 23 Jul 2000 15:47:23 EDT
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: Samuel Paik <[EMAIL PROTECTED]>
Subject: Re: Proving continued possession of a file
Date: Sun, 23 Jul 2000 19:56:49 GMT
Mark Wooding wrote:
> A while ago, I was asked to come up with some mechanism whereby a server
> could ascertain whether a client, which had previously transferred a
> particular file to the server, still had a copy of that file itself. I
> finally came up with something plausible (yet utterly impractical)
> yesterday evening, and I thought I'd share it with the group.
I don't understand why you don't just have Alice ask Bob to compute
cryptographic hashes of random segments of the file.
Sam Paik
------------------------------
From: "Kasper Pedersen" <[EMAIL PROTECTED]>
Subject: Re: Proving continued possession of a file
Date: Sun, 23 Jul 2000 22:19:59 GMT
"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.
But it could be simple. A sends B a 64 bit key, B uses it for a cipher in
countermode, gets, say, 64 indexes (mod filesize), does a hash. 64 bit in
both directions. can't be much less network traffic, and probably faster
than long math.
/Kasper
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Compression & Encryption in FISHYLAND
Reply-To: [EMAIL PROTECTED]
Date: Sun, 23 Jul 2000 22:25:29 GMT
Kurt Shoens <[EMAIL PROTECTED]> wrote:
: I was going to respond point by point but I realized I had nothing new to
: add. Instead, what I'll do is to state your position to make sure I've
: got it straight. [snip]
Your summary seems to cover my position quite well. I don't think I have
much of significance to add to it.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: "J.P." <[EMAIL PROTECTED]>
Subject: please take a look at my scheme...
Date: Mon, 24 Jul 2000 01:19:40 +0200
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.
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:
<snip> { Explanation of
}
for f[1]:=0 to 255 do { f[1]= 1st ASCII-value in the 2x2 box
}
begin { so f[2]= 2nd value,
}
f[2]:=x[5]-f[1]; { x[5]= 5th ASCII-value in the encrypted
block }
f[3]:=x[2]-f[1]; { minus the key-values
}
f[4]:=x[3]-f[2];
if (f[1]+f[4]=x[1]) and
(f[1]+f[3]=x[2]) and
(f[2]+f[4]=x[3]) and
(f[2]+f[3]=x[4]) and
(f[2]+f[1]=x[5]) and
(f[4]+f[3]=x[6]) and
(f[1]+f[2]+f[3]+f[4]=x[7]) then
begin
write(file2,chr(f[1]));
write(file2,chr(f[2]));
write(file2,chr(f[3]));
write(file2,chr(f[4]));
end;
<snip>
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.
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.
- 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.
Maybe if I increase the box/matrix size, and thus the key size
it will be harder to crack...
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 ! Then i'll just drop the experiment
and spend my time on something more usefull ;)
Well, that's it for now
Jan paul
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: 8 bit block ciphers
Date: 23 Jul 2000 16:55:36 -0700
Mack <[EMAIL PROTECTED]> wrote:
> That is what I am looking for mathematical or encryption
> methods of producing a 256 byte permutations.
> No shuffling please.
Why not use shuffling? It's the obvious answer.
If you have some extra constraints, it seems hard to answer the
question without knowing what they may be.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: 8 bit block ciphers
Date: 23 Jul 2000 16:58:46 -0700
Mack <[EMAIL PROTECTED]> wrote:
> I am looking for something that could be implemented without
> having the entire table in memory. For example only using
> 32 bytes. This prevents shuffling from being useful.
>
> I am looking for something that will take a 32 byte key
> and convert it to an 8 bit permutation. The permutation
> should have a good non-linearity, good avalanche and
> a good differential table. It should also be invertable.
> Methods that use fewer key bytes are acceptable.
> Basically it has to be a good 8-bit encryption method.
Why not use a Feistel network, with a 4-bit F function?
Encrypt for, say, 100 rounds or so (it can't hurt). The
result requires a 16-nibble table for the F function, plus
space to store the key.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Practical application of Ciphersaber (Was: RC4-- repetition length?)
Date: Sun, 23 Jul 2000 16:51:18 -0700
Guy Macon <[EMAIL PROTECTED]> wrote in message
news:8lfi4b$[EMAIL PROTECTED]...
>
> Great info! I hope that you don't mind a few questions.
> I am not a crypto (or math!) expert.
I also hope you are not going to design a real-life system based on what a
couple of guys on sci.crypt said, but you will check it out, right?
> 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.
Ummm, I hope that what's built into silicon is only part of the key you
present to the underlying RC4 cipher -- that the rest of the key is supplied
by the user or a public-key system and is transmitted to the receiver
through some out-of-band mechanism. If the entire RC4 key is embedded into
the chip, then it will always generate the same keystream, and that's easy
to break. If you generate the rest of the key randomly on chip, and
transmit it as salt, then all an attacker needs to break your systems is one
of your chips.
I'm personally ignorant of Ciphersaber, and so it may address this...
>
> 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?
Shouldn't be. If you sent zero data rather than random data, then an
attacker could use the known weaknesses to determine if, in a multigigabyte
span, if you sent a large number of messages or not, and do some traffic
analysis based on that. With random data, that really isn't a problem,
unless you might send a huge number of messages (gigabytes worth), and they
have extremely low entropy.
Oh, and how do you handle the case where one side goes down (loses power,
say)?
If you use 10 bit bytes, you may want to consider 10 bit RC4 -- that is, a
version with 1024 permutation elements, and all arithmetic done modulo 1024.
Every analysis of RC4 that I've seen that addresses this indicates that the
security gets better as the number of bits increase.
>
> >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?
The weaknesses I mentioned appear to be independent of passphrase. Certain
passphrases (such as ones where the first two bytes sum to zero mod 256)
cause artifacts to occur in the beginning of the keystream (which is why
recommendation 3 is given). Other than that, there is no known reason to
prefer one passphrase over another (except, of course, for guessability
reasons).
>
> >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).
You're fine. He said "designing your own stream cipher". You're not doing
that, you're implementing a stream cipher -- one that has already been
designed, and have been analyzed somewhat already, without any serious
weakness being published yet.
--
poncho
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Crypto jokes? (potentially OT)
Date: 23 Jul 2000 17:07:46 -0700
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> The idea that when an idea is independently discovered by
> multiple researchers, the first one to reach print gets all
> the credit has always been screwy.
Well, that's not been my experience of how the academic
world tends to work. In my experience, when two groups
simultaneously publish independent work that reaches the
same conclusion, they share the credit. In this case,
the word "simultaneous" often allows the two publications
to be separated by as much as a year or so.
But it has always been the case that if you discover
something, and wait _over two decades_ before publishing,
while someone else beats you to the punch, you won't get
credit. That's precisely as it should be, in my opinion.
Suppose Diffie, Hellman, Merkle, Rivest, Shamir, Adleman, et. al
had sat on their discoveries for 20 years before publishing,
while the spy agencies published immediately (in the 70's).
Then the spy agencies would have gotten all the credit, and
DH, M, RSA, etc. would have gotten none. That's also as it
should be, in my opinion.
Science advances through publication, and credit is the
incentive to publish.
------------------------------
** 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
******************************
