Cryptography-Digest Digest #719, Volume #12 Tue, 19 Sep 00 17:13:00 EDT
Contents:
Re: RC4: Tradeoff key/initialization vector size? ([EMAIL PROTECTED])
Parity Checking in DES (Brian Boorman)
Re: RC4: Tradeoff key/initialization vector size? (Paul Rubin)
Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption [an alternative
intorduction] ("Kostadin Bajalcaliev")
Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption ("Kostadin
Bajalcaliev")
Re: transformation completeness and avalanche effect ("Stanley")
Re: RC4: Tradeoff key/initialization vector size? (David A. Wagner)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RC4: Tradeoff key/initialization vector size?
Date: Tue, 19 Sep 2000 19:04:08 GMT
In article <8q2mt0$lle$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> In article <8q2aa6$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Guy Macon) wrote:
> > Tom St Denis wrote:
> > >
> > > David Crick <[EMAIL PROTECTED]> wrote:
> > >>
> > >> From the CipherSaber[-1] documentation
> (http://ciphersaber.gurus.com)
> > >>
> > >> The user key is a text string, rather than a hex value, because
> > >> humans are more likely to be able to memorize a text string with
> > >> sufficient entropy. To leave room for the initialization vector,
> > >> the length of the user key must be less than 246 bytes. To insure
> > >> adequate mixing of the initialization vector and user key, we
> > >> recommend you select a user key of 54 bytes or less.
> > >
> > >I would strongly recommend against using ASCII text as the key for
> > >RC4. You should really hash it first.
> > >
> >
> > I believe that the implementation of RC4 described on the web
> > page [ http://ciphersaber.gurus.com ] is secure without any
> > such hashing. Ciphersaber has withstood a lot of analysis
> > and attacks so far.
>
> The problem with using ascii data in the RC4 key schedule (assuming you still use
>it) is that alot of the swaps will
> not use the high bits randomly such as
>
> y = (y + + S[x]) mod 256
>
> The high bit of Key[x] will never be set, the values of Key[] are also terribly
>limited making them a poor choice
> for a good random RC4 key.
>
> If you hash it the values of Key[] will take on 0-255 almost perfectly distributed
>(assuming all is well).
>
> Tom
>
My goal in designing CipherSaber was to create a strong encryption system
that was so simple anyone with programming skills could implement it --
from memory if necessary. RC4's self-hashing properties are very
valuable in this regard. Also CipherSaber's extreme simplicity makes it
easy to audit, something that most crypto systems lack to day. And its
small size allows it to be run on any computer out there, including hand-
held calculators.
There are two indices that determine each swap. One, x in your notation,
is simply incremented. It is important that the other index, y, be well
distributed. This is accomplished in part by adding in the previous value
of y as you show in your formula. After a few swaps, y become very well
randomized. Also as the key setup progresses, there is an increasing
probability that the S[x] value that is added into the calculation is the
result of a previous swap.
It is far from clear that hashing the user key improves the security of
RC4. Hashing the key does not increase entropy. It does compress the key,
however. A typical CipherSaber key might average 35 characters. Add to
that a 10-byte random IV gives 45 characters. If a 128-bit hash is used,
as is typical, the key is reduced to 16 bytes. These 16 bytes are then
used 16 times in a fixed cyclic pattern to help determine the swaps. That
is hardly a "perfectly distributed" RC4 key stream. Using the ascii
values of the user key stirs in the entropy more slowly, but since there
are no know attacks that fully break RC4 either way, it is difficult to
say if that is a weakness or a strength. Using ascii keys does eliminate
all known classes of weak keys that I am aware of.
Of course one could use a hash function as a pesudorandom number
generator, with the user key as seed, to form a 256-byte RC4 key. As far
as I know, no one does this.
Most people who look closely at RC4 conclude that the later swaps are far
better randomized than the early swaps and that RC4 could be improved by
having more swaps during setup. I proposed Ciphersaber-2 which simply
increases the number of cycles in the RC-4 setup by some agreed-upon
factor of 256. Others have pointed out that increasing the number of
swaps in the RC4 setup to 256+N, while replacing the key with zero after
the initial 256 swaps, is equivalent to discarding the first N cypher
bytes in conventional RC4. This has the advantage of allowing one to say
that no change has been made to RC4. Either approach is far simpler than
adding a hash function and should eliminate any lingering concerns you
have about using ascii keys.
Arnold Reinhold
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Brian Boorman <[EMAIL PROTECTED]>
Subject: Parity Checking in DES
Date: Tue, 19 Sep 2000 19:40:00 GMT
Does anyone know what the parity checking algorithm is that is used on
hardware implementations?
The basic information I have is that the parity bits are stored in a
register, and fed into a parity tree along with bits from the C register
during rounds 10 & 11 and bits from the D register during rounds 12 &
13. Somehow this ends up in a parity register that reads "0111" if the
parity is ok, any other pattern is an error. I have not been able to
find any other details. It is not in the FIPS pubs other than a listing
of interface lines for the NIST hardware module that shows a parity
error output.
I need to implement this functional block as part of a replacement
hardware device I am designing, and I have to match the timing.
Any help appreciated!
--
Brian C. Boorman
Senior Engineer
Harris RF Communications
Rochester, NY 14610
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: RC4: Tradeoff key/initialization vector size?
Date: 19 Sep 2000 12:46:14 -0700
[EMAIL PROTECTED] writes:
> It is far from clear that hashing the user key improves the security of RC4.
If hashing doesn't help, then RC4 would be a very simple and fast
secure hash function all by itself. So why does anyone bother with
SHA?
------------------------------
From: "Kostadin Bajalcaliev" <[EMAIL PROTECTED]>
Subject: Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption [an
alternative intorduction]
Date: Tue, 19 Sep 2000 21:39:02 +0200
I inserted my answer in the text.
Mok-Kong Shen wrote in message <[EMAIL PROTECTED]>...
>
>
>Kostadin Bajalcaliev wrote:
>>
>[snip]
>> I hope you will find a little time to read my thesis, it is not the
regular
>> amateur-eureka-work.
>
>I have looked at your paper. The following are my comments:
>
>You have apparently thought that a function must be something
>written as a common mathematical expression like x^3+5. This
>is not true. Every mapping from one set to another set
>defines a function. In the discrete case, a function can
>be given by a table and there is no need to give a nice
>mathematical expression to describe it. If a blackbox
>delivers an ouput for each input, then it realizes a
>function. (The output for the same input may even be different
>at different times, but we shall not go that far here.)
Not at all, i agree that any maping from one set to another is function, but
it is very anpractical solution. Let the balck box accept 64-bit number in
and produce a 64-bit number as output. Since the box is assumed to exist in
the real world it is imossible to map it there are to many entries. Even
more there is some algorithm in side that make the transformation (if we
exculed random mapings). In order to analize this box we need to find the
algo inside. Maping it will be of no use.
>A piece of code in the programming language, normally one
>having as header 'function', gives the explicit steps
>of computation and realizes a function. That in such code
>one uses different constructs of the programming languages
>like 'if', 'case' to determine exactly what to do (among
>a number of options) in any concrete situation (cf. your
>example with the case construct) is what every programmer
>has been doing. Thus I am afraid that your newly constructed
>term 'quasi-function' is very confusing.
>
This second oppinion is somthing closer to definition of function in
general. Function is an algorithm that executing finit number of steps make
some transformation over the input or more theoreticly map the set of input
values into the set of output values. May be the term Quasi Algorithms is
not the lakyest choise but i thing it is an existing form. If you expand any
function into elementar steps (let say in ASM code) than it is easy to
notice that each step (instruction / operation) care 2 different types of
information in it, what should be done, and what are the argments
(operators). If the the operation is abstracted than we have a structure
that specifed by the order of step the kind of operation taking place in
each step and operand, but which operation is realy taking place in those
steps in unkown. Any algorithm have a skeleton, vertainly not all the
operations from the steps can be abstracted but most of tham can. In the
thsis there is a simple exmaple, a polynom function (they are not the only
king of functions). Let say f(x)=ax^2 + bx +c a simple equante of 2nd
degree. there are 5 operation inside, if we abstract tham we can write
Qf(x)=a o x o 2 o b o x o c where o is any operation. second function
g(x)=a+x-2+b-xc have the same skeleton only different operations are placed
in side. Qf is what I named quasi algorithm, becuase it determine a finit
class of functions, all of them will hace the same skeleton but very
different properties. The cryptographycal significance of this is explained
in the thesis.
>Polymorphism has been known in computer science since
>decades, though much popularized only after C++. Already
>in Algol68 one can use a datatype 'union' such that at
>runtime one can obtain first the type and then the value
>of an object and with these determine what is to be
>computed next. Polymorphic Types have been much studied
>by researchers of the functional languages. In procedural
>languages, ADA and C++ are two recent examples that much
>deploy polymorphism, with ADA having parametric types and
>generics and C++ having classes, inheritence and dynamic
>binding.
>
there is nothing common between Polymorph encryption and polymorphism in
programing languages, even some analogies can be found.
>Restricting ourselves now to matters of crypto, it is
>true that, as you mentioned, the use of data dependent
>rotations, substitutions and S-boxes can be advantageous.
>All these can, however, be subsumed under the concept
>'variability'. If a cipher is not 'fixed' like DES but
>has its components (e.g. S-boxes) different for
>different messages or even dynamically modified during
>encryption processing (e.g. a PRNG-driven cipher with
>feedback to PRNG), then the opponent is in general in an
>evidently much more difficult position to do the analysis.
>As you mentioned, techniques like differential analysis
>would no longer function. That's why I have many times
>in the past propagated the 'principle of variability'
>(my terminology) and suggested the use of parametrized
>ciphers (where the user has choice of different
>parameters, e.g. round numbers, optional processing
>steps, etc.) as well as dynamic random selection of
>encryption algorithms (see the thread of 28th May),
>which latter you also deal with in your paper.
>
I am happy you are one of propagater of "principle of variability", i will
be glad to read some of your works if possible. However my intention
formulating Polymorph encryption was to give a theoretical model of this
variability. Quasi algorithms are just the mathematical model.
>It is true that the well-known ciphers don't have
>variability or have only little variability. Thus
>suggesting introducing variability by dynamically
>changing the type of operators in expressions to be
>computed, as you have done, is in fact a good idea.
>(There have been use of such in some ciphers, though.)
>However, on the other hand, I believe you should
>avoid using the terms 'quasi-algorithm' (any piece of
>program that computes something and terminates is an
>'algorithm', there is nothing quasi) and 'quasi-
>function' (as explained above).
>
A expalined this prior, but Quasi Algorithms are unable to compute anything,
That why i introduce the phi notation, Phi(F,sigma,x) is an algorithm but F
the skeleton certainly is not.
Thanks for your coments i hope to continie this conversation.
>M. K. Shen
>---------------------------
>http://home.t-online.de/home/mok-kong.shen
------------------------------
From: "Kostadin Bajalcaliev" <[EMAIL PROTECTED]>
Subject: Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption
Date: Tue, 19 Sep 2000 21:58:30 +0200
Even Mr. Savard should be the proper responder let try clear some things
that i can.
Terry Ritter wrote in message <[EMAIL PROTECTED]>...
>
>On Tue, 19 Sep 2000 14:57:01 GMT, in
><[EMAIL PROTECTED]>, in sci.crypt
>[EMAIL PROTECTED] (John Savard) wrote:
>
>>[...]
>>The specific type of polymorphism in Konstantin Bajalcaliev's designs,
>>though, as you can see from looking at Quadibloc II and the others of
>>my designs which use it, was basically added almost as an
>>afterthought, which is why it is present only in such a rudimentary
>>form.
>
>I have looked, but end up more confused than when I started: Exactly
>what is it about this "specific type of polymorphism" which
>distinguishes from prior work? What is the process at issue:
>combining, mixing, what? Are we talking streams or blocks or what?
>
We are talking about general aproach in block cipher design. I have read
readed your work about Dynamic Substitution, even my cipher SQ1 implemt the
same ideas I must pay the credit to you since you have first describet that
approach in stream cipher desing, or more corectly strenghing the cipher.
That is the taching point in our works about stream ciphers. What I have
done plus Dynamic Sunbstitution is formulation of Information Lose Theory
that give a theoretical backgound to evaluate the security of a given
function especialy stream cipher. The thesis is available at
http://home.cyberarmy.com/kbajalc/algo/sq.
Now back to block ciphers.
>
>>If one thinks of not simply choosing between +, -, XOR, and
>>multiplication, but of choosing from a large collection of Latin
>>squares, there is of course Terry Ritter to think of, but I don't
>>think he ever made the choice of Latin square _data_ dependent.
>
>I would say that +, -, XOR and so-on are functions which happen to be
>convenient for math, but which each represent just a single
>possibility from among the universe of reversible combining functions.
>
>The advantage of the Latin square structure is to support *any*
>*possible* fixed discrete reversible combining function (of a given
>size) which has statistical balance with respect to both inputs. I
>find the literature quite persuasive with respect to the weakness of
>combining functions which are not balanced.
>
>On the other hand, my Dynamic Substitution does support a similar
>combining effect, continuous change, and statistical balance, in a
>much smaller table. The table is changed by transposition as selected
>by input data, which might be seen as both "polymorphic" and
>data-dependent. But I have no idea whether this is similar to the
>mentioned designs.
>
Dynamic substitution is a form of polymorphic design. But the polymorph
encryption and it mathematical model, the Quasi Algorithms are somthin more
general. The idea is very simple, to abstract the skeleton of the algorithm.
Function is an algorithm that executing finit number of steps to make
some transformation over the input or more theoreticly map the set of input
values into the set of output values. May be the term Quasi Algorithms is
not the lakyest choise but i thing it is an existing form. If you expand any
function into elementar steps (let say in ASM code) than it is easy to
notice that each step (instruction / operation) care 2 different types of
information in it, what should be done, and what are the argments
(operators). If the the operation is abstracted than we have a structure
that specifed by the order of step the kind of operation taking place in
each step and operand, but which operation is realy taking place in those
steps in unkown. Any algorithm have a skeleton, certainly not all the
operations from the steps can be abstracted but most of tham can. In the
thsis there is a simple exmaple, a polynom function (they are not the only
king of functions). Let say f(x)=ax^2 + bx +c a simple equante of 2nd
degree. there are 5 operation inside, if we abstract tham we can write
Qf(x)=a o x o 2 o b o x o c where o is any operation. second function
g(x)=a+x-2+b-xc have the same skeleton only different operations are placed
in side. Qf is what I named quasi algorithm, becuase it determine a finit
class of functions, all of them will have the same skeleton but very
different properties. The cryptographycal significance of this is explained
in the thesis.
Latin sqares can be used as operations also, o can be any possible maping
from R^2 to R (or some other appropriet set usualy No).
>One might consider a vector consisting of every possible Latin square,
>but to the same extent that we can implement it, we limit ourselves.
>A reason to select from among a huge universe of possibilities is that
>opponents gain no advantage from any pre-selection we may make. So if
>we have a subset that can be implemented, we have thrown away the
>advantage of having a large universe of possibilities, at least during
>operation. We might select a random subset for any particular
>message, but of course this is fundamentally just polyalphabetic.
>
>
>>My suspicion is that polymorphism has been around a long time, but
>>mostly in amateur designs.
>
>Exactly how is a cipher distinguished as being an "amateur design"?
>
>I claim that any such concept is fundamentally unscientific: A design
>is what it is, and not who did it. It can only matter who did it if
>we have no idea how to evaluate the result. And if we don't, then,
>realistically, those doing it probably don't either.
>
I fully support what you state here but in reality everyone make a
difference between somthing designed by well known scientiest and may be the
same thing by someone less known. Even this discrimination make me angry it
is the reallity and we must ajust.
>
>>But there may be something in the publicly
>>known history of cryptography that is properly considered to be its
>>origin.
>>
>>John Savard
>>http://home.ecn.ab.ca/~jsavard/crypto.htm
>
>---
>Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
>Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
>
------------------------------
From: "Stanley" <[EMAIL PROTECTED]>
Subject: Re: transformation completeness and avalanche effect
Date: Tue, 19 Sep 2000 21:24:20 +0100
Andru,
Could you explain why DES encryption = T(p XOR k) and decryption=U(c) XOR k?
Stanley
"Andru Luvisi" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Stanley" <[EMAIL PROTECTED]> writes:
> > Hi,
> >
> > I wonder if anyone could answer the question below?
> > If a (symmetric) cipher that exhibits transformation completeness and
have
> > good avalanche effect, does it necessary to be a good cipher(I mean its
> > security strength is substantial)? Thanks.
> >
> > Stanley
>
> Nope. Taking a variation on a previous post of mine, let's say we
> call T(x) DES encryption with an all zero key, and U(x) be DES
> decryption with an all zero key. Let's make our algorithm be:
>
> Encryption: c = E_k(p) = T(p XOR k)
> Decryption: p = D_k(c) = U(c) XOR k
>
> Good avalanche, yes, but totally insecure against a known plaintext
> attack. If we know c and p, we just compute p XOR U(c) and we have
> the key k.
>
> Andru
> --
> Andru Luvisi, Programmer/Analyst
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: RC4: Tradeoff key/initialization vector size?
Date: 19 Sep 2000 13:46:11 -0700
In article <8q8dao$85j$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> It is far from clear that hashing the user key improves the security of RC4.
It's pretty clear to me! Look, for instance, at Andrew Roos'
weak-key and related-key attacks on RC4 for examples of why you should
feel concerned about applications that don't pre-hash their RC4 keys.
------------------------------
** 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
******************************
