Cryptography-Digest Digest #277, Volume #12 Mon, 24 Jul 00 04:13:00 EDT
Contents:
Re: Random Appearance (Mack)
Re: Proving continued possession of a file (David A. Wagner)
Re: 8 bit block ciphers (David A. Wagner)
Re: RC4-- repetition length? ("Scott Fluhrer")
Re: RC4 free for noncommercial ? (Runu Knips)
Re: 8 bit block ciphers (Boris Kazak)
Re: 8 bit block ciphers (Runu Knips)
Re: 8 bit block ciphers (Mack)
Re: 8 bit block ciphers (Runu Knips)
Re: 8 bit block ciphers (Mack)
Re: 8 bit block ciphers (Mack)
Re: Q: Cascading multiple block algorithms (Mok-Kong Shen)
Re: please take a look at my scheme... (Mok-Kong Shen)
Re: Can Anyone Recomend A Good Intro Text (Mok-Kong Shen)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Random Appearance
Date: 24 Jul 2000 06:15:21 GMT
>
>"THE PAD MAY BE REUSED????"
>
>Which part on "One Time" are you having trouble understanding?
>
In any scheme it is possible for mistakes to happen.
If a OTP is reused by accident or design it is subject
to a known-plaintext attack.
>>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.
>
>
This thread started out as an inquiry about a cryto system that produced
output that looked 'normal'. I gave an example of such a system
that proved useful in practice.
It is not perfect but it did work. A crypto system does not have to be
'perfect' to be useful.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Proving continued possession of a file
Date: 23 Jul 2000 23:21:37 -0700
Mark Wooding <[EMAIL PROTECTED]> 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.
>
> Let's call the file's data M, and we'll suppose that Alice is running
> the server, and Bob is running the client. Last week, Alice knows that
> Bob had the file M, and he sent it to her. This week, Bob claims to
> still have the file, but Alice isn't convinced.
Did you want a one-shot solution, or did you want the server to be
able to repeat this verification some arbitrary number of times not
known in advance?
If you want a one-shot solution, here's a very simple protocol:
Last week:
B->A: M
Alice picks h randomly from H, a family of 2-universal hash functions,
computes h(M), and stores it.
This week:
A->B: h
B->A: h(M)
Alice checks that the hash Bob sent matches what she stored last week.
Cost: O(1) storage, O(1) bandwidth. Bob's computational workload is
not so bad -- essentially, the cost to read M in from disk again.
If you know in advance that you'll want to repeat the verification
protocol n times, Alice can pick h_1,..,h_n, etc. Cost: O(n) storage,
O(1) bandwidth per verification.
The (exceedingly clever!) protocol you proposed has the nice property
that it has O(1) storage and O(1) bandwidth per verification, and the
verification protocol can be performed any number of times. However,
the tradeoff is that Bob's computational costs get noticeably higher.
Note that there are ad-hoc tradeoffs that, in practice, probably allow
to reduce Bob's computational workload without hurting security too much.
Divide the message into d pieces, M_1,..,M_d. Last week, Alice should
have stored an independent verifier for each piece. This week, Alice
picks an index i in {1,2,..,d} at random, sends i to Bob, and executes
the verification protocol on M_i with Bob. For higher confidence, this
may be repeated r times. The result is that Alice's storage costs are
increased by a factor of up to d, bandwidth per verification goes up by
a factor of r, and Bob's workload goes down by a factor of d/r.
The security analysis of the above ad-hoc mechanism is a bit more complex.
Suppose Bob wants to fool Alice, and is willing to use storage space
proportional to a fraction p of the size of M. Suppose that the original
original verification protocol has probability q of error. Then the
probability that Bob fools Alice in the modified variant is at most
(p(1-q)+q)^r, which goes as something like p^r if q is small. Thus, to
obtain some fixed security level, it suffices to take r = O(1/log(1/p)).
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: 8 bit block ciphers
Date: 23 Jul 2000 23:30:25 -0700
Mack <[EMAIL PROTECTED]> wrote:
> >> I am looking for something that will take a 32 byte key
> >> and convert it to an 8 bit permutation.
> >
> >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.
>
> That is basically what I am looking for. But does anyone
> have a good one?
With 100 rounds, it probably takes some work to come up with something
which is not a good one! :-)
No, I highly doubt you will find anyone who has a good one. This is not
a normal thing to want to do. But you should be able to steal, say, a
Serpent S-box or something for the F function, and you're off to the races.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: RC4-- repetition length?
Date: Sun, 23 Jul 2000 23:15:32 -0700
Joseph Ashwood <[EMAIL PROTECTED]> wrote in message
news:eWyvDAT9$GA.233@cpmsnbbsa07...
> But you forget, with a stream cipher of the nature of RC4,
> there is no entropy being added after the initial keying.
> That means that you get diminishing amounts of randomness in
> the pad as it gets longer. It's easy to state that with a
> pad with say 7.9 bits of randomness per byte, it's basically
> unbreakable, but at any length RC4 can have no more than
> 2048 bits of total entropy, at 2048 bytes, there is 1 bit
> per byte, at 2 gigabytes there is 1/1024 of one bit of
> entropy per byte, that's small enough that it should be
> breakable. Either argument should lead to the fact that at 2
> gigabytes RC4 can be broken, I just don't know how to do it.
That argument makes no sense, unless you are talking about a computationally
unbounded adversary. Quadruple Serpent (that is, the block cipher defined
by iterating 4 copies of the Serpent block cipher, each with an independant
256 bit key) run in counter mode is a stream cipher that has no more than
1024+128 bits of total entropy, and so by the above analysis should be far
easier to break. But, if you have the foggiest clue that it is even
slightly breakable, even with 2 gigabytes of keystream, I suggest you let
NIST know right away...
Note: I'm not claiming RC4 is as secure as Serpent. I am claiming that the
above analysis is just as applicable to Serpent, or Quadruple Serpent.
--
poncho
------------------------------
Date: Mon, 24 Jul 2000 08:32:59 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: RC4 free for noncommercial ?
David Hopwood wrote:
> Runu Knips wrote:
> > Runu Knips wrote:
> > > I'm looking for a good & free stream cipher algorithm.
> > > Does anybody have a suggestion ?
> >
> > My crypto book states that 'RC4 requires a license fee
> > for commercial use'.
>
> That's wrong, RC4 is not patented. Which crypto book?
My crypto book doesn't state it is. It only says that
'Even if juristical doubtable, you have to pay a
license for using RC4. At least that will be cheaper
than a lawsuit.'
(My still one and only crypto book is a german one,
'Abendteuer Kryptologie', translated to english:
'Adventure Cryptgraphy', by Reinhard Wobst, Addison-
Wesley, ISBN 3-8273-1193-4, 69,90 DM).
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: 8 bit block ciphers
Date: Mon, 24 Jul 2000 06:49:20 GMT
Mack wrote:
>
> Still not quite what I am looking for. The
> 8-bit block cipher is to be used as an S-box.
>
> Mack
> Remove njunk123 from name to reply by e-mail
=====================
Clarity of explanations is not one of your strong points...
Tell me if I understand you correctly:
You need an algorithmic presentation of a random-looking
bijective 8-bit S-box, preferably such, that it would be
easily keyed and difficult for attacker to reconstruct.
Keep in mind, please, that in any case a dedicated
attacker will reverse-engineer all the 256 entries in the
table, so no matter how complicated will be the encryption,
256 trial plaintexts will be all that is needed.
This said, the simplest S-box is just a XOR or addition
mod 256. This S-box is fast, requires only 1 byte in RAM.
A little more complicated is multiplication (mod 257).
This operation is always possible, because 257 is a prime
number. In order to represent all numbers from 0 to 255
there exists a convention, that for the purposes of
modular multiplication 0 is treated as 256, then there is
no real 0 in the multiplication routine. This operation
requires about 4 bytes in ROM. You must also compute the
multiplicative inverse of your key byte for decryption.
If you want to see a routine of modular multiplication
in a practical cipher, look at the code of IDEA. There
you will find multiplication mod 65537, you will easily
figure out how it does relate to your task at hand.
In the cipher SAFER (one of AES contestants) there are
some more examples of algorithmic 8-bit S-boxes, based on
raising some fixed number to integer power and on discrete
logarithms.
If I understood your problem incorrectly, sorry.
Best wishes BNK
------------------------------
Date: Mon, 24 Jul 2000 08:51:06 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: 8 bit block ciphers
Mack wrote:
> Does anyone have any information on 8 bit block
> ciphers? I don't mean simply shuffling an array.
What do talk about ? A block cipher can always be
mathematically represented as an array (a different
one for each different key, of course), only that
the arrays addressed by 64 bit or even 128 bit
would exceed all available memory of all computers
in the world. But for 8 bit, the array has only
2**8 = 256 members, each of 8 bit or 1 byte.
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: 8 bit block ciphers
Date: 24 Jul 2000 06:56:59 GMT
>Mack <[EMAIL PROTECTED]> wrote:
>> >> I am looking for something that will take a 32 byte key
>> >> and convert it to an 8 bit permutation.
>> >
>> >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.
>>
>> That is basically what I am looking for. But does anyone
>> have a good one?
>
>With 100 rounds, it probably takes some work to come up with something
>which is not a good one! :-)
To use the entire 32 byte key you would need 64 rounds. So 100 rounds
is not that far off base.
>
>No, I highly doubt you will find anyone who has a good one. This is not
>a normal thing to want to do. But you should be able to steal, say, a
>Serpent S-box or something for the F function, and you're off to the races.
>
Since Serpent stole them from DES I guess I could just use those.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
Date: Mon, 24 Jul 2000 08:55:02 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: 8 bit block ciphers
Mack wrote:
> >Mack 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.
> >Using less than 256 bytes of code?
> >Your "requirements" don't make sense.
> Less than 256 bytes of RAM. Think embedded
> applications.
AAAAAAH ! You don't want a 8 bit block cipher (something
completely insecure), you want a block cipher which can be
implemented on 8 bit low end architectures !!!
Just use Twofish. Can be implemented with 64 byte of RAM.
Is one of the most secure modern block ciphers (together
with Blowfish and Serpent), has 128 bit blocks and key
sizes between 128 and 256 bit.
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: 8 bit block ciphers
Date: 24 Jul 2000 07:05:28 GMT
>Mack wrote:
>>
>> Still not quite what I am looking for. The
>> 8-bit block cipher is to be used as an S-box.
>>
>> Mack
>> Remove njunk123 from name to reply by e-mail
>---------------------
>Clarity of explanations is not one of your strong points...
> Tell me if I understand you correctly:
> You need an algorithmic presentation of a random-looking
>bijective 8-bit S-box, preferably such, that it would be
>easily keyed and difficult for attacker to reconstruct.
> Keep in mind, please, that in any case a dedicated
>attacker will reverse-engineer all the 256 entries in the
>table, so no matter how complicated will be the encryption,
>256 trial plaintexts will be all that is needed.
>
> This said, the simplest S-box is just a XOR or addition
>mod 256. This S-box is fast, requires only 1 byte in RAM.
> A little more complicated is multiplication (mod 257).
>This operation is always possible, because 257 is a prime
>number. In order to represent all numbers from 0 to 255
>there exists a convention, that for the purposes of
>modular multiplication 0 is treated as 256, then there is
>no real 0 in the multiplication routine. This operation
>requires about 4 bytes in ROM. You must also compute the
>multiplicative inverse of your key byte for decryption.
> If you want to see a routine of modular multiplication
>in a practical cipher, look at the code of IDEA. There
>you will find multiplication mod 65537, you will easily
>figure out how it does relate to your task at hand.
These are basically the same as the work by nyberg and
Beth and Ding at Eurocrypt '93 which may be the way
to go.
> In the cipher SAFER (one of AES contestants) there are
>some more examples of algorithmic 8-bit S-boxes, based on
>raising some fixed number to integer power and on discrete
>logarithms.
This I haven't looked at.
>
> If I understood your problem incorrectly, sorry.
>
>Best wishes BNK
>
Is ok .. it helped me define it more specifically.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: 8 bit block ciphers
Date: 24 Jul 2000 07:10:05 GMT
>Mack wrote:
>> >Mack 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.
>
>> >Using less than 256 bytes of code?
>> >Your "requirements" don't make sense.
>
>> Less than 256 bytes of RAM. Think embedded
>> applications.
>
>AAAAAAH ! You don't want a 8 bit block cipher (something
>completely insecure), you want a block cipher which can be
>implemented on 8 bit low end architectures !!!
>
>Just use Twofish. Can be implemented with 64 byte of RAM.
>Is one of the most secure modern block ciphers (together
>with Blowfish and Serpent), has 128 bit blocks and key
>sizes between 128 and 256 bit.
>
Accept I don't have 64 bytes to play with.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Cascading multiple block algorithms
Date: Mon, 24 Jul 2000 09:47:20 +0200
Bryan Olson wrote:
> Mok-Kong Shen wrote:
> > Mok-Kong Shen wrote:
> > > In Schneier's AC, p.367, about cascading two block ciphers it
> > > is stated:
> > >
> > > If the second algorithm is vulnerable to a chosen-plaintext
> > > attack, then the first algorithm might facilitate that
> > > attack and make the second algorithm vulnerable to a known-
> > > plaintext attack when used in a cascade.
> >
> [...]
> > Now that input is the output from the first algorithm. It
> > cannot be directly chosen but only indireclty through choosing
> > input to the first algorithm. This indirectness, assuming that
> > the first algorithm has any strength at all, evidently means
> > that the said attack is now more difficult.
>
> The statement doesn't say there's any realistic chance of
> this happening. It's a possibility we cannot disprove, and
> we can create contrived situations to illustrate it, but we
> certainly don't expect it with reasonable ciphers.
>
> In known plaintext attack, the attacker is limited to the
> given plaintext distribution. Putting another cipher in
> front could result in a distribution much worse for the
> second cipher. Suppose you have a block cipher that's very
> strong if the first bit of the plaintext block is always 0,
> but terrible when the first bit is one. It's vulnerable to
> chosen plaintext, but when used to send ASCII text it's
> strong.
However, 'chosen-plaintext attack' without further qualification
means to the reader that it is the general case, i.e. the analyst
can choose ANY plaintext he likes. With an intermediate (first)
algorithm, his choice of the input to the second algorithm is
evidently limited, unless he has already cracked the first algorithm
somehow. Anyway, the presence of the first algorithm (which is at
issue in the present context) can't have any negative effect on
the second algorithm in aspect of its susceptibility to chosen-
plaintext attack (with the term understood as such).
While AC does refer to the attack as a 'potential attack', it says:
If you let someone lese specify any algorithm which is
used on you message before encryption, then you had
better be sure that your encryption will withstand a
chose-plaintext attack.
which sounds like that the possibility discussed is not entirely
imaginary/theoretical but could indeed very well happen in actual
practice.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: please take a look at my scheme...
Date: Mon, 24 Jul 2000 09:47:35 +0200
"J.P." wrote:
> 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".
You should get yourself familiar with Hill's cipher, before devising your
own algorithm employing matrix operations.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Can Anyone Recomend A Good Intro Text
Date: Mon, 24 Jul 2000 09:49:53 +0200
Wade Reiber wrote:
> 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".
If you want another, have a look at F. L. Bauer's Decrypted Secrets,
published by Springer Verlag.
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
******************************
