Cryptography-Digest Digest #313, Volume #13 Tue, 12 Dec 00 10:13:01 EST
Contents:
Re: Unguessable sequence of unique integers? (David Schwartz)
Re: important programming languages (Andre van Straaten)
Re: Array shuffling (Mok-Kong Shen)
Re: Array shuffling (Paul Crowley)
Re: important programming languages (Mok-Kong Shen)
Re: Security of Netscape Messenger PGP PlugIn (Johnny Bravo)
Re: Unguessable sequence of unique integers? (Paul Crowley)
Re: important programming languages ("Brian Gladman")
Rijndael / AES Q ("kihdip")
Request: A Compiled Rijndael DLL Pretty Please :) (Mike Vaughn)
On using larger substitutions (Mok-Kong Shen)
Re: important programming languages ([EMAIL PROTECTED])
Re: important programming languages ([EMAIL PROTECTED])
Re: ElGamal questions ([EMAIL PROTECTED])
Re: important programming languages ([EMAIL PROTECTED])
Re: Rijndael / AES Q (Mok-Kong Shen)
Re: Unguessable sequence of unique integers? (Mok-Kong Shen)
----------------------------------------------------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Unguessable sequence of unique integers?
Date: Tue, 12 Dec 2000 02:11:46 -0800
John Savard wrote:
>
> On Tue, 12 Dec 2000 00:16:57 GMT, Johan Hanson
> <[EMAIL PROTECTED]> wrote, in part:
>
> >I suppose I could do this by using a simple counter
> >and encrypting the result with a symmetric algorithm.
>
> That generally would be believed to be the only safe way of doing
> this; however, the problem exists that if you use a block cipher with
> a 32-bit block, to guarantee uniqueness of the 32-bit units output, it
> is not believed that a block cipher with so short a block can be made
> secure.
One could develop a 32-bit symmetric block encryption algorithm with a
key of any size. If the encryption algorithm has no defects, there
should be no better way of breaking it (from less than about 2^24
outputs) than brute-forcing the key.
DS
------------------------------
From: Andre van Straaten <[EMAIL PROTECTED]>
Subject: Re: important programming languages
Date: 12 Dec 2000 04:44:00 -0600
Brian Gladman <[EMAIL PROTECTED]> wrote:
> "Bob Silverman" <[EMAIL PROTECTED]> wrote in message
> news:9143le$fbd$[EMAIL PROTECTED]...
>> In article <lqbZ5.12088$I5.128757@stones>,
>> "Brian Gladman" <[EMAIL PROTECTED]> wrote:
>> >
>> > "Bob Silverman" <[EMAIL PROTECTED]> wrote in message
>> > news:913eav$tgi$[EMAIL PROTECTED]...
>> > > In article <IaaZ5.12042$I5.127023@stones>,
>> > > "Brian Gladman" <[EMAIL PROTECTED]> wrote:
>> > > > So if you truly consider this to be no more than 'a minor nitpick'
>> > > you are
>> > > > illustrating your own lack of knowledge of the full breadth of
>> > > requirements
>> > > > for cryptographic algorithm implementation in the real world.
>> > >
>> > > ROTFL.
>> >
>> > You might consider ignorance a laughing matter but I do not.
>>
>> What I was laughing about was the suggestion that I might be
>> ignorant about implementing crypto algorithms in the real world.
>>
>> And yours is showing. I have implemented crypto software and
>> computational number theory software on more different platforms
>> and architectures than I can count;
>>
>> I have written computational code on Z80's Z8000's
>> 68000's , 68010, 68020, 80286, 80386, Pentium, PDP-11, VAX, DEC-10
>> IBM-370, Cray-1, RS6000, R3000, R10000, PA-RISC, Alpha's , DEC-20,
>> Burroughs 6700, I860, plus some parallel architectures which no longer
>> exist: Intel Hypercube, Thinking Machines CM2, CM5. I have written
>> such code in a multitude of assemblers, in Algol, in Fortran IV
>> and Fortran '77. In Bliss, In C, in C++, in Franz Lisp and Common
>> Lisp. etc. etc. And of course, under so many different OS's that
>> I don't remember all of them.....
>>
>> I also have some engineering responsibilities for BSAFE.
>>
>> The idea that I might be ignorant about what is needed to make
>> crypto code work across a variety of platforms is hilarious.
> Portability is often an important requirement which encryption source code
> has to meet. In consequence you should know that portability often
> 'matters' in language choice even for encryption algorithms - which from
> your earlier statement:
>> There is really only one language that matters for encryption:
>>
>> assembler.
> you clearly don't.
> Do I now have to conclude that you have done a lot of encryption
> implementation but have learnt very little from it?
> Brian Gladman
No, if he is an Assembler guru, he ports the code by himself.
;-)
The point is, if hand-optimized code is wanted, that's generally
where money doesn't matter, or if you have huge sales figures in
embedded devices, you don't have to rely on standard compilers.
In this case, you have some highly paid people sitting around
and thinking about the optimization of their hand-crafted code.
Software development is a wide field with many niches the same as
cryptography.
(That's why this thread gets inflated now. I'll try to keep quiet
from now on.)
-- avs
Andre van Straaten
http://www.vanstraatensoft.com
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Array shuffling
Date: Tue, 12 Dec 2000 11:52:39 +0100
Benjamin Goldberg wrote:
>
> Nondeterministic amount of time to complete means that we cannot
> garuntee that the number of bits used will have any particular bound,
> and that the amount of time used will not have any particular bound.
But that means the user would sometimes wait very very long,
wondering whether there might have been some other errors
(hardware malfunction etc.) or whether the algorithm indeed
doesn't terminate within the period that he can afford to
wait. (Are there cases of real non-termination?) That
would lead to an acceptance problem, I am afraid. Is the
the probability of that occuring negligible? Thanks.
M. K. Shen
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Array shuffling
Date: Tue, 12 Dec 2000 11:31:47 GMT
lcs Mixmaster Remailer wrote:
> The proof of unbiasedness is easy, by induction.
I think this proof is insufficient. It proves that for any given
element, each final position is equally likely. This would also be true
of a shuffling algorithm that picked an unbiased r in 0..n-1 and rotated
the entire array by that many steps. However, I also now think the
algorithm is unbiased and I'll see if I can make a better proof
sometime: ISTM that this algorithm dynamically assigns each element a
random number between 0 and 1 and does a radix sort on that number.
I haven't been able to work out the expected number of random bits drawn
from theory, so I wrote Python programs to simulate three methods:
traditional: draws integers 2..n from modran
partitioning: Goldberg's method
perfect: draws n! from modran
modran is implemented thus:
def modran(a):
x = 0L
l = 1L
while 1:
if l >= a:
if x < a:
return x
x = x - a
l = l - a
x = x * 2 + randombit()
l = l * 2
(1L is just 1 represented as a bignum)
Linux's /dev/urandom is used as a source of random bits; this is
generally considered a very high quality RNG.
Note that my implementations don't actually shuffle anything, they just
draw the appropriate number of bits.
Here's the number of bits drawn when I shuffle a 256-element array 100
times:
bash-2.03$ ./perfect
Bits used: 168400
bash-2.03$ ./traditional
Bits used: 193667
bash-2.03$ ./partitioning
Bits used: 210944
This suggests that Goldberg's method makes less efficient use of random
bits than the traditional method.
If anyone wants source I'll make a web page.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: important programming languages
Date: Tue, 12 Dec 2000 12:48:44 +0100
Andre van Straaten wrote:
>
[snip]
> Fortran and C have generally the best performance, in case you really
> are interested in speed.
True.
> A last word to Lisp or Scheme (a stripped down dialect of Lisp).
> Some mathematicians write their proofs in these languages.
> They are full-fledged general-purpose languages, too.
I conjecture that functional languages which generally
allow dynamic generation of program codes to be executed
provide a potentially exploitable feature for crypto, in that
the encryption system could easily modify itself at runtime
in ways that are hard for the analyst to follow. BTW, since
a large number of PLs have been mentioned in this thread, I
suppose that it is appropriate to add ADA, which is a nice
PL in my humble view.
M. K. Shen
------------------------------
From: Johnny Bravo <[EMAIL PROTECTED]>
Crossposted-To: alt.security.PGP
Subject: Re: Security of Netscape Messenger PGP PlugIn
Date: Tue, 12 Dec 2000 06:58:24 -0800
On Tue, 12 Dec 2000 08:49:27 GMT, [EMAIL PROTECTED] wrote:
>Hi,
>
>Has anyone heard of this plug in for using PGP with Netscape Messenger:
>http://bear-software.freeservers.com/ ?
>
>Is this any good and are there any risks (security wise) in using this ?
There is a definite risk, no source code.
Best case scenario, the program is exactly what it claims.
Worst case scenario, it modifies your PGP encryption (either
deliberately or accidentaly) to a smaller subset of session keys,
leaving your messages open to decryption through brute force of the
smaller search space while still keeping everything else in the
program fully operational.
Not that I have even a shred of evidence for any of the cases. They
do remain a possibility and better safe than sorry is a crypto motto.
--
Best Wishes,
Johnny Bravo
BAAWA Knight, EAC - Temporal Adjustments Division
"The most merciful thing in the world, I think, is the inability
of the human mind to correlate all its contents." - HP Lovecraft
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Unguessable sequence of unique integers?
Date: Tue, 12 Dec 2000 12:18:33 GMT
Bob Silverman wrote:
>
> In article <[EMAIL PROTECTED]>,
> moc.qit@nahoj wrote:
> > Hello.
> >
> > I am looking for an algorithm for a generator of a sequence
> > of unique and unguessable 32-bit integers.
> > The number of integers created by the sequence must be
> > very large, i.e. in the 32-bit range and no two values
> > in the sequence must overlap until a fairly large number
> > (a minimum of 2^24 or so) of values have been found.
>
> Impossible.
Sure, but it's possible the real need can be met all the same. He
doesn't say that the sequence must be indistinguisable from a truly
random sequence, only that the values must be unguessable. If he's only
using 2^24 or so values from the sequence, it sounds like he wants a
block cipher with a 32 bit block size.
Now, I don't know of any such ciphers "on the shelf", so one would have
to be designed, which is of course a tricky endeavour. I would suggest
taking a look at Rijndael. If you take out the "ShiftRow" step,
Rijndael operates on each column independently, so it's obvious how a
one-column Rijndael should work. We're not told that it needs to be
fast, so lots of rounds would be good insurance against a total lack of
serious cryptanalysis - after 64 rounds, even the weakest adequate round
function starts to look good. The Rijndael key schedule could be used,
or something stronger, like using the key to key Rijndael itself and
then using Rijndael in counter mode to produce the keys for this new
block cipher.
This is all off the top of my head and worth roughly what you paid for
it. It's a shame we don't have any good variable-size block ciphers
that scale down to a single bit. Yes, this does make sense to think
about, imagine related-key attacks against such a cipher.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: important programming languages
Date: Tue, 12 Dec 2000 12:37:48 -0000
"Andre van Straaten" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Brian Gladman <[EMAIL PROTECTED]> wrote:
> > "Bob Silverman" <[EMAIL PROTECTED]> wrote in message
> > news:9143le$fbd$[EMAIL PROTECTED]...
[snip]
> >> I also have some engineering responsibilities for BSAFE.
> >>
> >> The idea that I might be ignorant about what is needed to make
> >> crypto code work across a variety of platforms is hilarious.
>
> > Portability is often an important requirement which encryption source
code
> > has to meet. In consequence you should know that portability often
> > 'matters' in language choice even for encryption algorithms - which from
> > your earlier statement:
>
> >> There is really only one language that matters for encryption:
> >>
> >> assembler.
>
> > you clearly don't.
>
> > Do I now have to conclude that you have done a lot of encryption
> > implementation but have learnt very little from it?
>
> > Brian Gladman
>
> No, if he is an Assembler guru, he ports the code by himself.
> ;-)
>
> The point is, if hand-optimized code is wanted, that's generally
> where money doesn't matter, or if you have huge sales figures in
> embedded devices, you don't have to rely on standard compilers.
>
> In this case, you have some highly paid people sitting around
> and thinking about the optimization of their hand-crafted code.
>
> Software development is a wide field with many niches the same as
> cryptography.
>
> (That's why this thread gets inflated now. I'll try to keep quiet
> from now on.)
Please don't leave on my account since I have no problem with what you are
saying.
As I have already said, I see hardware, assembler and high level language
implementations all having their place depending on the nature of the
requirements that have to be met. This is a stance that I would normally
expect Bob Silverman to be able to agree with but for some reason he does
not.
I believe that there are situations where high level language implementation
does 'matter' and quote as my example code that needs to meet a portability
requirement. There are already a number of encryption libraries in real use
where much of the encryption code is written in C partly for this reason.
So to put the issue in its shortest form, the question is: "are there
significant requirements for which the software implementation of encryption
algorithms in any other language than assembler matters?"
Bob's view is 'no', my view is 'yes'.
Others following this debate can judge for themselves which of us is right.
Brian Gladman
------------------------------
From: "kihdip" <[EMAIL PROTECTED]>
Subject: Rijndael / AES Q
Date: Tue, 12 Dec 2000 14:05:44 +0100
Reading the Rijndael Block Cipher document, I have a question concerning the
ByteSub transformation:
The two transformations in 4.2.1 describes the construction of the 8 bit -
S-boxes.
Both transformations applies to construct the INV S-boxes (for decryption)
and only the second transformation applies to construct S-boxes for
encryption.
Correct ??
Thanks in advance
Kim
------------------------------
From: Mike Vaughn <"vaughnmt"@@@home.com>
Subject: Request: A Compiled Rijndael DLL Pretty Please :)
Date: Tue, 12 Dec 2000 13:56:09 GMT
Hi,
I am a mediumly skilled VB enthusiast and I would like to play around
with Rijndael, but after two days of searching all I could find was
plenty of C++ source. I was amazed that no-one thought to provide a
pre-compiled DLL for users without MSC++ V6. I suppose it has something
to do with trust ( if I didn't compile it then I really don't know
what's in there, etc).
Could some kindly, honorable person please email Rijndael.dll (or
whatever it is called) to me so I can start experimenting with it? It
would mean so much to me. If you could also provide just a couple of
helpful pointers on how the functions are used that would be a real
blessing. Something like: "First you make the key by... and then you
encode it by... and decode it by..."
BTW, does anyone know if it has been ported to VB yet? If I had VB
source then I could do everything by myself!
I apologize if I am asking for too much, you guys are great and I don't
want to overstep my bounds.
Thank you so much in advance!
Mike Vaughn
vaughnmt@@home.com (remove 2nd "@")
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: On using larger substitutions
Date: Tue, 12 Dec 2000 15:14:00 +0100
A general 16-bit substitution table is commonly considered
impractical because of the large storage space required,
not to say using a number of such tables. On the other
hand, the technique of Playfair offers extremely compact
storage, though with the trade-off of realizing only very
special substitutions. One could help a bit through using
a version employing two matrices. Further one could
concatenate several Playfairs. In situations where one
could be satisfied with the quality of such substitutions,
the following scheme, which requires some more storage but
is more flexible and straightforward to code, may be of
interest:
One generates four 8-bit substitution tables. The two
bytes of the given 16 bits are first transformed by the
first two tables respectively. The result is circularly
shifted 4 bits and the remaining two substitution tables
are applied in the same manner.
One could through recursion obtain in this way a 32-bit
substitution, employing sixteen 8-bit substitution tables.
M. K. Shen
===============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: important programming languages
Date: Tue, 12 Dec 2000 14:20:32 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
> Neither Java nor Perl are "more or less interpreted", IMO.
> In particular, Java has had JITs for years, now. These days, you get a
> runtime-profiniling, optimising JIT with practically any decent JVM.
> Java is very frequently compiled to native code. About the only place
> Java is interpreted these days is in embedded systems - where there'e no
> room for a JIT.
Well, it's always only a matter of time before this bugaboo comes
up. Any language can be either interpreted or compiled, depending on
the implementation. (And given a liberal enough interpretation of the
words) In fact, most of them today blur the line sufficently that it's
an almost meaningless distinction in the general cases.
In Java's case, JIT runtimes, the GCC backend, and even Sun's plan for
world domination via Java chips are all appealing as speed
boosters. Even the plain old jvm is alot faster than most people seem
to give it credit for though.
In perl's case, when used for processing text (as opposed to trying to
write a first person shooter or something else it's wholey unsuited
for) many operations are hoisted off into C by the interpreter
anyway. In this case, odds are the optomised C version in the perl
binary is better than what you'd crank out yourself on the first try.
Now, don't get me wrong, neither is going to outperform hand-tuned
assembler as a general rule. Nor are their compilers going to produce
code as fast as the typcial C compiler, given that we're looking at
about 30 years of continual improvement in C compilers and
substantially less than that for either of the others.
On the other hand, the original post to me sounded like someone with
no programming experience at all asking which languages to start with
given an eye on understanding cryptography. For that, I can't see the
problem with using something slightly more expressive to implement toy
versions of algorithms. In java, for example, you get all the io and
padding for free, which lets you concentrate soley on the actual
cipher. Simiarly, in perl a population count of a 256bit string takes
.0002 sec/call when called as a function, and before any
optomisation. For "playing around" that two lines of code beats the
equivalent assembler hands down.
Would I expect someone to implement a library function to do the same
thing via an embedded perl interpreter? Hell no. Would I immediately
dismiss someone studying an algorithm in perl as non serious because
they're not using assembler? Hell no.
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: important programming languages
Date: Tue, 12 Dec 2000 14:26:57 GMT
John Savard <[EMAIL PROTECTED]> wrote:
> But you're saying Perl is a compiler? I had thought it was an
> interpreter, even if it was bigger and more compiler-like than Awk;
> that would be one of the reasons for putting an $ in front of every
> variable (an awkwardness that keeps many people away from Perl,
> despite the exellencies that many others have noted in it).
It's sitting on the fence, like all modern interpreters. The script is
compiled at startup into a more executable format. The $ nonsense is
actually to indicate a scalar value, rather than some other type.
Most of the time, you're in C anyway, because the regexp package, io,
etc are part of the perl binary. You do, however, pay big for some
statements. A goto, for example, parses the entire script again
scanning from the top for a matching label. As a general rule, a
script either runs as fast or faster than a compiled program, or
pathologicaly slower, with an average of just a bit slower.
Yes, thank god there _is_ a simple to use profiler. ;)
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: ElGamal questions
Date: Tue, 12 Dec 2000 14:17:57 GMT
> If you are truly performance driven you will not use ElGamal. Instead
> develop a key negotiation scheme using a one-time generated shared DH
> key and use "symmetric" encryption for all further communications.
>
> I did this in my old Peekboov2 program. Two people would make a
shared
> DH key and I would hash the shared-secret (big 2048-bit number) plus a
> random IV (I appended to the message) to make a session key to encrypt
> the message. Once you make the shared secret sending messages only
> required to hash some text and encrypt via a fast symmetric cipher.
>
> Tom
Hi Tom, thanks for your answer.
But what I want to do is to protect some information (as passwords)
and other sensible information in a database. And what I need is that
some people can store the data (encrypted with public key) and
other can read it (using the private key). That why I want to use a
public/private schema, and given that the data to encrypted is about
the length of a 128 bit key I thought that treating the data as the
session key will be a good idea.
Jorge
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: important programming languages
Date: Tue, 12 Dec 2000 14:38:15 GMT
Andre van Straaten <[EMAIL PROTECTED]> wrote:
> The adavantage of C++ comes with larger projects. For math is C often
> faster. OO brings a little overhead which has an impact only for fast
> real-time applications.
Although, there have been occasional interesting attempts at using
templates for mathematically intensive work with promising
results. The down side being the resulting code is usually 100%
unreadable to mathemeticians, and anyone else for that matter.
> Besides some simply crypto tools you better forget, is there the NumPy
> package.
I think that actually appeared about the same time as the rather quiet
template obsession. Unlike C++, however, I think the syntax benefits
may actually give python a chance at being a sort of fortran
replacement for some people.
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Rijndael / AES Q
Date: Tue, 12 Dec 2000 15:42:20 +0100
kihdip wrote:
>
> Reading the Rijndael Block Cipher document, I have a question concerning the
> ByteSub transformation:
>
> The two transformations in 4.2.1 describes the construction of the 8 bit -
> S-boxes.
> Both transformations applies to construct the INV S-boxes (for decryption)
> and only the second transformation applies to construct S-boxes for
> encryption.
>
> Correct ??
No. The document states clearly that both the inverse in
GF(2^8) and the affine transformation are applied in
encryption and decryption, though in different order.
Otherwise the matter evidently wouldn't work.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Unguessable sequence of unique integers?
Date: Tue, 12 Dec 2000 15:42:32 +0100
Paul Crowley wrote:
>
[snip]
> It's a shame we don't have any good variable-size block ciphers
> that scale down to a single bit. Yes, this does make sense to think
> about, imagine related-key attacks against such a cipher.
Scaling a block cipher (which has a fixed key) down to a
single bit would mean either the identity mapping or the
bit inverse and is evidently barely useful. This extreme
case illustrates why it is advantageous to use larger
blocks (and in the (other) extreme case of treating the
entire message as a whole). On the other hand, one can have
a PRNG-controlled block encryption, which on scaling down
to a single bit becomes a stream cipher (in the restricted
sense). Thus combination of stream and block encryption
techniques certainly offers more flexibility in cipher
design than either technique alone.
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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
