Cryptography-Digest Digest #312, Volume #13 Tue, 12 Dec 00 05:13:00 EST
Contents:
Re: Unguessable sequence of unique integers? (Benjamin Goldberg)
Re: Array shuffling (Bryan Olson)
Re: Unguessable sequence of unique integers? (Bryan Olson)
Re: Unguessable sequence of unique integers? (John Savard)
Re: important programming languages (John Savard)
Re: Array shuffling ("Matt Timmermans")
Re: Array shuffling (Benjamin Goldberg)
Re: Array shuffling (David Schwartz)
Re: important programming languages (Benjamin Goldberg)
Re: important programming languages (Tuomas Pellonpera)
Security of Netscape Messenger PGP PlugIn ([EMAIL PROTECTED])
Re: important programming languages ("Brian Gladman")
Re: Bilderbergs --- see also who are there from Finland ... these are people who
have sold Finland out .... of course Henry Kissinger and Bill Clinton have been in
Bilderbergs too (Andre van Straaten)
Re: important programming languages (David Schwartz)
Re: Unguessable sequence of unique integers? (Bryan Olson)
----------------------------------------------------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Unguessable sequence of unique integers?
Date: Tue, 12 Dec 2000 04:34:40 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.
>
> (1) If it is truly generated by an algorithm, as opposed to a
> (say) true white noise generator, then the sequence can be guessed
> or deduced.
While this is technically true, it is possible to make a generator which
is so difficult to guess that more known/chosen plaintexts are needed
than are available. For example, suppose you use a 16 bit fiestel,
whose F function is an 8 bit fiestell, using the AES sbox as the F
function. Use 8 rounds at each level, and a 64 byte random key (with
the key generated once, from some sort of TRBG). The time it takes to
guess the key is fantastically longer than the time it takes to encrypt
all possible values of a 32 bit counter.
There will be no collisions until the counter turns over.
> (2) Any truly random or pseudo random 32-bit sequence will have,
> with high probability a collision after 2^16 values. The probability
> of a collision after 2^20 is near certainty. Look up the
> birthday problem.
While what you say is true about a truly random 32-bit sequence, it is
not necessarily true about psuedo-random sequences. What I described
above is a form of PRNG, and it has no collisions. For a NORMAL prng,
yes, the birthday problem holds, but my scheme is intentionally designed
to avoid collisions, while maintaining a good distribution of values,
and staying nearly unguessable.
> What you want does not exist.
>
> --
> Bob Silverman
> "You can lead a horse's ass to knowledge, but you can't make him
> think"
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Array shuffling
Date: Tue, 12 Dec 2000 04:45:51 GMT
Benjamin Goldberg wrote:
> Instead of comparing N! to 2**(N*log(N)), try comparing N*log(N) to
> log(N!).
What's the base of the log? From context, Goldberg clearly
meant the log base-2 (commonly written "lg"). But the
notation "log" without a statement of the base conventionally
means the log base 10. Base 10 would make the "Instead of
comparing" suggestion invalid, since we'd be taking the log
base 10 of one expression and the log base 2 of the other.
> log(N!) is equal to the sum, from i=1 to N, of log(i). For
> example, log(5!) == log(5)+log(4)+log(3)+log(2)+log(1), which is much
> less than 5*log(5).
"Much less" is debatable. Though the difference between N
log(N) and log(N!) grows arbitrarily large as N grows, by
proportion they get closer together:
lim N->inf N log(N) / log(N!) = 1
> From this, we can see that 2**log(N!) does NOT
> exceed 2**(N*log(N)), and in fact the opposite is true.
Shen's assertion was
> > N! ultimately exceeds by far 2^(N*log(N)).
Shen is right for the log base 10, Goldberg for the
log base 2.
Goldberg's claim about his algorithm: "it should use N*log(N)
bits on average" is not exact for either base. It is true
that it should use Theta(N log(N)) bits on average, and in
that case the base of the log doesn't matter.
Scott Fluhrer (correctly) wrote of an optimal algorithm:
| Using a maximally efficient modran function, this takes an
| expected log2(N!)+O(1) random bits.
As a corollary to some of Fluhrer's analysis, we can show
Goldberg's algorithm uses more than log2(N!)+O(1) random bits.
The expected number of partitions of length 3 the algorithm
will be recursively process will grow without bound as N
grows, and the expected number of random bits used by each
such call exceeds the optimal by a constant.
I conjecture, (i.e. don't know) that the ratio of expected
bits used in Goldberg's algorithm to lg(N!) goes to 1 for
large N. That's a weaker statement than that it's lg(N!)+O(1)
but stronger than Theta(lg(N!)).
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Unguessable sequence of unique integers?
Date: Tue, 12 Dec 2000 05:10:13 GMT
moc.qit@nahoj wrote:
> I am looking for an algorithm for a generator of a sequence
> of unique and unguessable 32-bit integers.
To be sure I understand: you want to iteratively generate the
elements of a pseudo-random permutation of 32-bit integers.
> I suppose I could do this by using a simple counter
> and encrypting the result with a symmetric algorithm.
Specifically, a secret-key block cipher with a 32-bit block.
> Is there a good freely available implementation of a simple
> algorithm?
I don't know of a good off-the-shelf 32-bit block cipher.
> is there any better way of creating the sequence?
I think your suggestion is probably as good as it gets. Other
methods are better for smaller permutations.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Unguessable sequence of unique integers?
Date: Tue, 12 Dec 2000 05:21:55 GMT
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.
>.. but more interestingly, is there any better way of creating
>the sequence?
Although one can have better stream generators than, say, the linear
congruential generator to produce a series of non-repeating numbers;
for example, there are _quadratic_ congruential generators that have
maximal period; I learned this a while back after asking the question
on this newsgroup; but none of those methods, with a 32-bit state and
the output of the entire state can really achieve any security at all.
If you want security, you need a bigger internal state, a bigger block
size, than 32 bits. So, if you need an absolute guarantee of
uniqueness over 2^24 outputs, you will just have to have an array with
2^24 elements over which you perform some sort of shuffle or check for
duplicates operation, if you want to use serious encryption methods
that are believed to be secure.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: important programming languages
Date: Tue, 12 Dec 2000 05:26:09 GMT
On Mon, 11 Dec 2000 23:58:22 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote, in
part:
>Neither Java nor Perl are "more or less interpreted", IMO.
Well, the JVM code still has to be compiled each time an applet is
executed, so there is an overhead that doesn't exist when the program
is compiled once before all the executions.
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).
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Array shuffling
Date: Tue, 12 Dec 2000 06:14:28 GMT
"David Schwartz" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> The higher bits of the state don't affect the lower ones, but the lower
> ones affect the higher ones, the higher ones affect the higher ones, and
> the output comes from the higher ones. So your argument that the period
> is at most 2^16 is incorrect.
It would be incorrect if I had actually said that. What I said was the the
lowest N bits of the state have a period at most 2^N, which is true.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Array shuffling
Date: Tue, 12 Dec 2000 07:53:57 GMT
Matt Timmermans wrote:
>
> "David Schwartz" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > The higher bits of the state don't affect the lower ones, but the
> > lower ones affect the higher ones, the higher ones affect the higher
> > ones, and the output comes from the higher ones. So your argument
> > that the period is at most 2^16 is incorrect.
>
> It would be incorrect if I had actually said that. What I said was
> the the lowest N bits of the state have a period at most 2^N, which is
> true.
And coupled with the fact that rand() outputs bits 17..32 of the state
(according to how you seem to be counting bits), the period of rand()
should be (and is, I think) 2**32.
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Array shuffling
Date: Tue, 12 Dec 2000 00:00:25 -0800
Matt Timmermans wrote:
> It would be incorrect if I had actually said that. What I said was the the
> lowest N bits of the state have a period at most 2^N, which is true.
You are literally correct. However, it's far from obvious that this is
necessarily a defect in the algorithm.
DS
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: important programming languages
Date: Tue, 12 Dec 2000 08:03:10 GMT
John Savard wrote:
>
> On Mon, 11 Dec 2000 23:58:22 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote, in
> part:
>
> >Neither Java nor Perl are "more or less interpreted", IMO.
>
> Well, the JVM code still has to be compiled each time an applet is
> executed, so there is an overhead that doesn't exist when the program
> is compiled once before all the executions.
>
> 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).
>From what I recall, Perl compiles the text script into it's own internal
form, much like Java compiles java text source into java bytecodes.
Perl's internal bytecodes are then interpreted, but just as a JVM even
without JIT is still significantly faster than a java source interpreter
[would be] (if one existed), so is the Perl bytecode interpreter faster
than a normal script interpreter.
Additionally, there may even be some Perl implementations which do
compile from the bytecode into machine language code, just like JIT.
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Tuomas Pellonpera <[EMAIL PROTECTED]>
Subject: Re: important programming languages
Date: Tue, 12 Dec 2000 08:01:14 GMT
Hi!
I'm thankful for all the tips, hints, personal opinions and pieces of
advice you have presented. (Although I would like to, I can't thank
everyone in detail.) I have learnt a lot, but one thing I knew already,
before this discussion. I was aware that there is no such thing as 'the
best programming language'. I admit I may have given such an impression;
looks like I didn't choose my words carefully enough. For that I
apologize.
Best wishes,
Tuomas
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: alt.security.PGP
Subject: Security of Netscape Messenger PGP PlugIn
Date: Tue, 12 Dec 2000 08:49:27 GMT
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 ?
Thank you in advance for your help,
Brice.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: important programming languages
Date: Tue, 12 Dec 2000 09:10:26 -0000
"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
------------------------------
From: Andre van Straaten <[EMAIL PROTECTED]>
Subject: Re: Bilderbergs --- see also who are there from Finland ... these are people
who have sold Finland out .... of course Henry Kissinger and Bill Clinton have been
in Bilderbergs too
Crossposted-To: alt.security,comp.security
Date: 12 Dec 2000 03:06:50 -0600
In sci.crypt Chris Ahlstrom <[EMAIL PROTECTED]> wrote:
> "Markku J. Saarelainen" wrote:
>>
>> http://ourworld.compuserve.com/homepages/grattan_healy/Bild-az-tab.html
>>
>> Ahlstr�m, Krister, President and CEO, Ahlstr�m Group
> Cool, almost the same spelling as my name! But you're message
> means nothing to me. Can you explain it? Thanks!
My hint: secret messaging via Markov chain algorithms, far better
than ROT26.
> Chris Ahlstrom
-- 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: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: important programming languages
Date: Tue, 12 Dec 2000 01:21:57 -0800
Bob Silverman wrote:
> There is really only one language that matters for encryption:
>
> assembler.
The _only_ advantage of assembler is speed. Since CPU speed is
increasing at a greater rate than pretty much anything else, this is
becoming less and less important. The advantages of portability, ease of
modification, and ease of verification will outweight the speed benefits
in all but extreme cases.
What percentage of the encryption code you deal with is written in
assembler? 5%? IMO, the best reason to learn assembler is not to program
in it, but to be able to understand it so you can see what your C code
is actually making the computer do.
DS
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Unguessable sequence of unique integers?
Date: Tue, 12 Dec 2000 09:38:40 GMT
John Savard wrote:
> Johan Hanson wrote:
> >I suppose I could do this
[generate unguessable 32-bit integers without repetition]
> > 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.
A 32-bit block cipher should be fine. The small-codebook
problem is the _only_ security issue that pushes us to
larger block sizes. That problem is irrelevant in this
case; what he wants is the permutation, not the cipher.
The reason we don't use 32-bit block ciphers is that they'd
be bad for normal encryption; they'd make great
pseudo-random 2^32 element permutation generators.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
