Cryptography-Digest Digest #648, Volume #13 Wed, 7 Feb 01 07:13:01 EST
Contents:
Re: Universal Maurer-Test ([EMAIL PROTECTED])
Re: CipherText patent still pending (Mok-Kong Shen)
Re: Phillo's alg is faster than index calculus (Mok-Kong Shen)
Re: Pseudo Random Number Generator (Mok-Kong Shen)
Re: On combining permutations and substitutions in encryption (Mok-Kong Shen)
Re: File encryption with Rijndael
Re: On combining permutations and substitutions in encryption (Benjamin Goldberg)
Re: Questions about Diffie-Hellman ([EMAIL PROTECTED])
Re: Encrypting Predictable Files (Benjamin Goldberg)
Re: Encrypting Predictable Files (Benjamin Goldberg)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Universal Maurer-Test
Date: Wed, 07 Feb 2001 10:58:50 GMT
The NIST implementation automatically calculates an adequate value for
L. Download the file sts-1.4.zip from http://csrc.nist.gov/rng/rng2.html
Should anyone be interested, I also have a Delphi implementation at
http://www.streamsec.com/prngtst.asp
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hello,
>
> has anyone a C oder C++ implementation of the
> "Universal Statistical Test for Random Bit Generators"
> (Ref.: J. Cryptology Vol. 5, No. 2, 1992, pp. 89-105)
> of Ueli Maurer for different values L
> of the blocksize.
>
> I have found an implementation for L=8, but
> no for an arbitrary L.
>
> Thanks,
> Bernhard Loehlein
>
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: CipherText patent still pending
Date: Wed, 07 Feb 2001 12:31:59 +0100
Bryan Olson wrote:
>
[snip]
> Hard to believe you are looking at the same world as am I.
> There's a huge need, and call, for crypto research. But a new
> symmetric cipher not known to be secure or insecure just makes
> a large pile bigger.
Remember that I was answering affimatively to your third
question. We were considering ciphers proposed to this
group which are mostly (I would say all, though some would
protest against my view for very understandable reasons)
done in the sense of excercise for purposes of learning as
you observed. That also explains why one extremely rarely
sees in the group names of authors who publish in high-grade
crypto journals. Yes, the pile gets bigger. But don't you
see that at schools the pupils are continuing to write
compositions (after you have left school)? Should they
stop writing?? It may be noted that there is a parallel
(monitored) group sci.crypt.research which is supposed to
be a forum for research stuffs. Since you apparently
pose a rather high standard on materials you read, I warmly
recommend you to switch to that group, thus saving you
your precious time to read much beginner level stuffs
that inevitably contain lots of shaffs or even nonsenses.
Those others who think that beginners could occassionally
present some interesting or even fairly useful/novel ideas
and have sufficient patience to earnestly discuss with
people at levels of knowledge not as eminent and exquisite as
themselves should however remain here in our group, I urge.
M. K. Shen
=======================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Phillo's alg is faster than index calculus
Date: Wed, 07 Feb 2001 12:32:04 +0100
[EMAIL PROTECTED] wrote:
>
[snip]
> So what do you think?
After you have apparently spend quite a bit of 'thinking',
I recommend you to do an excercise on a real-life example
to see how easy or difficult it is to do that computation
and eventually compare with other methods, instead of
'extrapolating' from a toy example through merely a 'thought'
process. (Don't argue too long about the quality of an
apple pie, taste it.) Please let us know, after you have
good success.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Pseudo Random Number Generator
Date: Wed, 07 Feb 2001 12:32:08 +0100
Bryan Olson wrote:
>
> Mok-Kong Shen wrote:
> > Bryan Olson wrote:
> > > Mok-Kong Shen wrote:
> >
> > > > What can be proved is the following:
> > > >
> > > > For m non-degenerate independent integer random variables
> > > > over [0,n-1] their sum mod n approaches a uniform random
> > > > variable as m increases. If one of the random varaible is
> > > > uniform, then any value of m results in a uniform random
> > > > variable.
> > >
> > > Counterexample: Lent n = 49, and the distribution of each
> > > variable be uniform over the 42 integers in [1..48] that are
> > > not divisible by 7, and zero elsewhere.
> >
> > That's what is excluded by 'non-degenerate'. Sorry, if
> > the term is not standard or common.
>
> Typical use of "degenerate" is for cases where a key defining
> property is fulfilled in a vacuous way. For example (the one
> I assumed) a random variable that only has one possible value
> is degenerate. I don't see anything degenerate about the
> distribution in my counter-example.
>
> What exactly does your usage of non-degenerate mean? Clearly
> divisibility by seven is not the only case.
If I consider, say, quadratic polynomials of the general
form ax^2+bx+c in a certain context, then cases where
a has the value 0 will generally be deemed degenerate.
I use the term in the same sense. A random variable
over [0, n-1] in general takes on all possible values
in the range, though some maybe with very low frequencies.
If certain values have frequencies of exact 0, then the
variable is equivalent to one over a smaller range
(and should be treated as one such) and hence is degenerate
with respect to the larger range.
M. K. Shen
=======================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On combining permutations and substitutions in encryption
Date: Wed, 07 Feb 2001 12:31:49 +0100
Terry Ritter wrote:
>
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
>
> >Terry Ritter wrote:
> >>
> >> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
> >>
> >> >[...]
> >> >It is interesting that you view whole file processing as
> >> >variable-size block ciphers (in view of the fact that
> >> >you have some patents on variable-size block ciphers,
> >> >if I remember what you wrote previously correctly).
> >>
> >> The cipher design is what it is. The patent is what it is. This is
> >> not really a viewpoint issue.
> >
> >The meaning of what you wrote above is not yet very clear
> >to me. A 'consideration' that whole file processing is a
> >block encryption is also what it is (as a view/fact). It
> >is not a trivial issue at all, for there is the very
> >serious question of possible infringement of your patents
> >(hopefully only in US currently) when one does whole file
> >processing in crypto.
>
> It is not "whole file processing" which defines a Variable Size Block
> Cipher, although of course one would expect that a VSBC could cover a
> full file. In practice, it may be more reasonable to set some maximum
> large-block size which will fit in memory, process that, then go on to
> another chunk, so huge files might be processed in chunks anyway.
> With respect to my VSBC patent, a particular structure is defined.
If one process bit per bit, or byte per byte, or block (of
any fixed size) per block, proceeding from one (any) end
of a message to the other end and repeat (i.e. do
superencipherment) many passes, would that be deemed doing
variable size block encryption and hence infringing on your
patents? If not, I am satisfied and have nothing to say.
Otherwise, the issue merits to be discussed in-depth in the
group, I believe. (see also below.)
>
> >Further, using e.g. CBC to chain blocks effectively makes
> >the whole message a 'block'. When one looks the proper
> >(small) block cipher as a component of a larger system,
> >then one is doing 'block' encryption, the whole message
> >being that (large) block, and one of 'variable' block size,
> >because the size of messages is in general not constant.
> >So block chaining in general would have possibly been in
> >conflict with your patents. If that is indeed the case,
> >it would be very important that all people concerned with
> >crypto know it, in fact much more important than Hitachi's
> >rotation.
>
> As I recall, CBC was in fact patented by IBM. That is not some verbal
> academic presentation in a small overseas meeting, but is instead
> prime published material that examiners are expected to know. Just
> getting an issued patent implies that it does not read on CBC. In
> particular, CBC is a one-way diffusion, but is only applied once;
> there is only one "layer."
>
> As far as I know, I was the first person in the world to publish the
> concept of a Variable Size Block Cipher, and my original sci.crypt
> post and the academic responses to that post are archived on my pages.
> My patent covers the technique for achieving VSBC's by the application
> of (at least) two one-way diffusion layers. Dependent claims cover
> confusion with diffusion, confusion in opposite directions, and so on.
>
> I have actually measured diffusion in many different VSBC structures.
> Normally, it is necessary to have at least 3 one-way diffusion layers
> before the system attains diffusion characteristics which approach a
> true block cipher. So when I design a VSBC, that is what I do. But
> from the patent it appears that others who do less are also covered.
>
> >Sorry for going a bit in-depth about this issue, for I
> >myself often do whole file processing and employ chaining
> >(and further once considered letting the user to have the
> >comfort of choosing the block size within an appropriate
> >range) and hence am particularly interested in it.
>
> Well, yeah, but we've been over this and over this. The issued patent
> is a legal document, and as such may have application beyond what the
> inventor expected. My VSBC patent has been on my web site for years;
> nowadays it is probably just as available from the US PTO site.
> Obviously, US patents do not apply in Europe.
>
> I understand that many academics feel that they don't need patents, so
> they don't need to know how to read patents. It seems amusing to find
> academics arguing from a position of ignorance about their intent to
> maintain that ignorance, but maybe academics can get away with that.
> You, however, obviously do need to learn how to read a patent.
>
> For infringement purposes, go to the claims. Read each claim and see
> if it will fit into ("read on") the proposed design. If the claims
> contain unusual words, it may be necessary to read the patent body to
> understand what those words meant to the inventor, and how they should
> be interpreted in a claim. Basically, if any design includes all
> parts of even one claim, it will infringe when manufactured, sold
> (including free distribution), or used. Extra parts around the basic
> design do not prevent infringement.
>
> The reason for having dependent claims is to further specialize an
> independent claim. So even if the independent claim is found in court
> to be too broad, the further-specialized dependent claims may still
> stand. But until things get to court, every issued claim has already
> been argued and approved by the government which issued the patent;
> all claims are thus assumed valid. If any claim reads on a design,
> manufacture, sale, and use are restricted to that permitted by the
> patent holder.
Let's consider the ancient autokey technique in its
(less preferable) form using cipher characters to process
the next characters (see Menezes et al.), does it differ
from what is done in CBC (in case done with modular
addition), excepting that instead of a unit of one character
(nowadays 8 bits) one has a block having 64 bits or more?
CBC is only a new name applied to an old technique. There
is nothing novel in my humble view. In classical crypto one
processes characterwise from the beginning of a message to
the end. One can superencipher, i.e. process in multiple
passes. That is all 'processing the whole file', treating
the whole as a 'block', if one wants to employ the term
'block'. (There is a proverb saying that to a hammer the
world is of all nails.) So from this consideration I
personally don't see any novelty in variable size block
encryption at all, sorry to say that. (Your patents may
indeed contain really novel features that are not related
to what is described above, I don't know. But the above
is definitely not novel.)
It might be true that CBC was patented in US, but that's
a clear indication of the lamentable situation of
patenting in US in my humble view, allowing all trivialies
(besides really good stuffs) be patented and without public
reviews, e.g. Hitachi's rotation, etc. etc.
M. K. Shen
========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: <[EMAIL PROTECTED]>
Subject: Re: File encryption with Rijndael
Date: Wed, 7 Feb 2001 06:37:50 -0500
On Wed, 7 Feb 2001, Marcin wrote:
> I have made available my tiny command line file encryption program based on
> Rijndael with 256 bit keys. Its coded in Java and freely distributed with
> source code at: http://www.optymalni.com/~marcin
> Any comments please direct to [EMAIL PROTECTED]
>
> Marcin
>
You might be interested in my assembler version, code length only
440 bytes for 256-bit keys, http://www.afn.org/~afn21533/tinyrijn.zip
which supports all 9 combinations of key and block sizes.
=============
My home page URL=http://www.afn.org/~afn21533/ Robert G. Durnal
Hosting RIJNDAEL, the AES winner, in CFB block [EMAIL PROTECTED]
chaining mode with key hashing. Executable is [EMAIL PROTECTED]
only 440 bytes. Download as tinyrijn.zip
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: On combining permutations and substitutions in encryption
Date: Wed, 07 Feb 2001 11:43:13 GMT
Matt Timmermans wrote:
>
> "Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > What do you mean the size of the input?
> >
> > Or, to put it another way, suppose you have AES with a 192 bit key.
> > Write the relationship between the key bits, the plaintext bits, and
> > the ciphertext bits as a 3SAT problem. Does this conversion take
> > polynomial in terms of 192, or superpolynomial in terms of 192? (I
> > think you've said the conversion takes polynomial time in terms of
> > 192, but I'm not sure.) If it takes polynomial time to convert,
> > then there cannot be more than polynomial terms in the 3SAT problem.
> > If it takes superpolynomial time to convert, then there may [or may
> > not] be a superpolynomial number of terms.
>
> Strictly speaking (though not as strictly as Bryan does, which is why
> I'm posting yet another response ;-), the reduction takes time
> polynomial in worst-case run time of the algorithm (AES, in this
> instance) for inputs of the given size. So (assuming key size
> unbounded), if the worst-case running time of AES(K,M) is polynomial
> in length(K)+length(M), then the question "AES(K,M)==C?" can be
> converted to 3-SAT in time polynomial in length(K)+length(M).
Wow. So if it can be proved that P=NP, then ALL ciphers which run in
polynomial time lose most of their security against known plaintext.
What a horrifying possibility.
--
A solution in hand is worth two in the book.
Who cares about birds and bushes?
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Questions about Diffie-Hellman
Date: Wed, 07 Feb 2001 11:38:14 GMT
I thought that it was comme-il-fait to choose a generator of a cyclic
subgroup <g> of Zp* instead of a generator of Zp*, just to avoid traces
of quadratic residues.
I.e. choose g = q**((p-1)/r) mod p, where q may be any number such that
GCD(q,p) = 1, and r is a large prime such that r|(p-1).
AFAIK all DH derivate protocols supports such choices of g without
modifications (although the DSA prime generation algorithm recommended
by NIST should be modified to allow larger values of r than 2**160).
In article <#b5eIFHkAHA.279@cpmsnbbsa07>,
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
> "Julian Morrison" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > 1) Can a wiretapper who sees *all* messages passed to and fro
figure out
> > the key?
> With properly chosen keys, no. The information the attacker would
have to
> use, and the equation that would have to be solved are:
> known
> p - a large prime, on the order of 512 bits or above for a strong
> implementation
> g - a generator value, this is generally a smaller prime
> /.../
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Encrypting Predictable Files
Date: Wed, 07 Feb 2001 11:54:33 GMT
Splaat23 wrote:
>
> Umm, I do recall saying that inserting the length of the file on the
> plaintext would solve the problem. Or using an escape code to signal
> the end of the message. Or sending the length in the clear. Or any
> number of other options.
>
> Reading thr rest of this thread, I see that I misunderstood the
> original topic. However, I'm not sure I see the usefulness of having a
> completely bijective file encryption process (as opposed to just the
> block cipher component, which is required for all).
There isn't one, really, except in David's imagination.
PS, if encryption is a bijection, and decryption is a bijection, then
encryption and decryption are both permutations. "Completely bijective"
is a nonsensical (and ambiguous) term, and could apply even to functions
which aren't permutations.
--
A solution in hand is worth two in the book.
Who cares about birds and bushes?
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Encrypting Predictable Files
Date: Wed, 07 Feb 2001 12:07:31 GMT
Joseph Ashwood wrote:
>
> "Bryan Olson" <[EMAIL PROTECTED]> wrote in message
> news:95plt8$o9q$[EMAIL PROTECTED]...
> > Paul Housley wrote:
> > [...]
> > > There are some parts of the files which are predictable.
> > [...]
> > > I am concerned that, by knowing what part of the file is
> > > supposed to decrypt to, this may help people to find the
> > > encryption key.
> > >
> > > Any advice, particularly concerning the RC4 algorithm?
> >
> > RC4 is designed to resist known-plaintext attacks, and so far
> > no one has shown it doesn't.
>
> However it also suffers from plaintext substitution, that is to say
> that if the plaintext is known it can be replaced with a different
> more desirable plaintext, this may or may not be a problem depending
> on the situation. Because of this I'd suggest using at a minimum an
> AllOrNothingTransform. Realistically that'll be as expensive as using
> a block cipher that doesn't suffer from this problem.
>
> > It is _not_ designed to encrypt multiple messages with the
> > same key. Always derive a new key RC4 key for each message.
>
> No argument at all, this is an absolute MUST.
> Joe
Suggesting an AONT seems a little bit silly as a way of strengthening a
cipher; not because it doesn't work, but because if it's a true AONT, it
provides such a HUGE increase in strength that almost anything you care
to follow it with becomes enough to be secure.
If you're going to introduce AONT into your system, you need almost
nothing else. Simply XORing your key with the AONT'd text is enough,
even for a fairly short key (provided that key's long enough to avoid
being brute forced).
--
A solution in hand is worth two in the book.
Who cares about birds and bushes?
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
