Cryptography-Digest Digest #321, Volume #13 Wed, 13 Dec 00 16:13:00 EST
Contents:
Re: Security of Netscape Messenger PGP PlugIn (John Myre)
Re: Sr. Cryptographer/mathematician (John Myre)
Re: Software PRNG.. (John Myre)
Re: (help) Its easier to break symetric alg. when ....? ([EMAIL PROTECTED])
Re: 64bit CRC (John Myre)
Re: YAPRNG (John Myre)
Re: YAPRNG (Richard Heathfield)
Re: Software PRNG.. (Jorgen Hedlund)
Re: STT stream cipher (update) (John Myre)
Re: Newbie (Richard Heathfield)
Re: YAPRNG (John Myre)
Re: Newbie (John Myre)
Re: Software PRNG.. (John Myre)
Re: Security of Netscape Messenger PGP PlugIn (Emrul)
Re: STT stream cipher (update) (David Schwartz)
Re: Software PRNG.. (David Schwartz)
Re: YAPRNG (David Wagner)
Re: Unguessable sequence of unique integers? (Bryan Olson)
Protocol for computer go (Francois Grieu)
Re: Virtual memory security hole? ("Harvey Rook")
----------------------------------------------------------------------------
From: John Myre <[EMAIL PROTECTED]>
Crossposted-To: alt.security.PGP
Subject: Re: Security of Netscape Messenger PGP PlugIn
Date: Wed, 13 Dec 2000 10:27:57 -0700
Johnny Bravo wrote:
<snip>
> Worst case scenario...
<snip>
I agree with your sentiments, but I thought I'd point out
that things could be much worse. An unknown binary could
do practically any evil thing you could imagine, beyond
slightly weakening the encryption strength. (C.f. worms,
viruses, etc. etc.)
JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Sr. Cryptographer/mathematician
Date: Wed, 13 Dec 2000 10:22:21 -0700
Tom St Denis wrote:
>
> In article <1ZrZ5.287$[EMAIL PROTECTED]>,
> "Matt Timmermans" <[EMAIL PROTECTED]> wrote:
> > Your rather gritty usenet manner is sometimes entertaining, Tom, but
> there
> > are many reasons to be more civil.
>
> "You're rather..." hehehehe... Just trying to have some fun.
<snip>
I'm not clear on something here. Do you seriously think
that Matt made a spelling error, which you gleefully get
to correct? Or, to be generous, perhaps you're attempting
some sort of pun? (To be clear: Matt's post is correct.)
You know, I remember when juvenile humor seemed funny; I
was a juvenile, of course. I wonder: am I headed towards
Silverman-esque grumpiness or does Tom need to grow up?
(Or, uh oh, am I already even grumpier?!)
JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Software PRNG..
Date: Wed, 13 Dec 2000 10:41:11 -0700
Richard Heathfield wrote:
>
> Jorgen Hedlund wrote:
<snip>
> > Although, I've a question about this term "biased", what do you mean
> > with that something is "biased"?
>
> I'd guess that it's analogous to a die numbered 1, 2, 3, 3, 4, 5 - and
> I'll be interested to see whether my guess is confirmed, or shot down in
> flames. :-)
More like a die with the normal numbers but not quite
"fair" - maybe slightly heavier to one side, or not exactly
cubical, or something like that. That is, your analogy is
apt, except for being misleading in the case of RC4 by
exaggerating more than I liked.
(Also, the RC4 bias is more complex than simply favoring
certain outputs more than others; Paul Crowley's web site
has excellent details.)
JM
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: (help) Its easier to break symetric alg. when ....?
Date: Wed, 13 Dec 2000 17:37:06 GMT
Thanks ....
Jorge
In article <9186mc$o4l$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hi,Imagine this situation. You have a process that encrypts
> data using a symetric algorithm that you know (lets say DES). You
> can encrypt anything you want. Will these variables (knowing the
> original message and the encrypted message) make it easier
> to find the key used to encrypt the data?
>
> thanks in advance for any reply
>
> Jorge
>
> Sent via Deja.com
> http://www.deja.com/
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: 64bit CRC
Date: Wed, 13 Dec 2000 10:47:31 -0700
Paul Schlyter wrote:
>
> In article <[EMAIL PROTECTED]>,
> Mihai Preda <[EMAIL PROTECTED]> wrote:
>
> > I need two independent 32bit fingerprints for a message. I think CRC
> > would be a good choice (I don't need security).
<snip>
>
> You could also choose
<snip>
Of course, making a choice depends, not just on what he says
he doesn't need ("security", whatever that means here), but
mainly on what he does need. Why would someone need two
"independant" fingerprints? And of course: "what are the
requirements on speed, code size, etc., etc.?"
JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: YAPRNG
Date: Wed, 13 Dec 2000 11:05:19 -0700
Richard Heathfield wrote:
>
> David Wagner wrote:
<snip>
> > Thus, your framework is not sufficient for security. The details matter.
<snip>
Why don't I amplify this a bit. Your framework is essentially
meaningless: if you don't know the details of the two PRNG's all
you have is one new PRNG whose details you still don't know. The
security could be anything. If you *do* know the details of the
component PRNG's, then you know the details of the combination,
and the security is in those details (maybe adequate, maybe not).
In nearly any practical situation, piling on complications helps
rather than hurts, but one is really just guessing without doing
real cryptanalysis. (And actually, even then we might have just
a more believable guess.)
JM
------------------------------
Date: Wed, 13 Dec 2000 18:39:17 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: YAPRNG
John Myre wrote:
>
> Richard Heathfield wrote:
> >
> > David Wagner wrote:
> <snip>
> > > Thus, your framework is not sufficient for security. The details matter.
> <snip>
>
> Why don't I amplify this a bit. Your framework is essentially
> meaningless: if you don't know the details of the two PRNG's all
> you have is one new PRNG whose details you still don't know. The
> security could be anything. If you *do* know the details of the
> component PRNG's, then you know the details of the combination,
> and the security is in those details (maybe adequate, maybe not).
>
> In nearly any practical situation, piling on complications helps
> rather than hurts,
ROT-13 twice, anyone? <g,d&r>
> but one is really just guessing without doing
> real cryptanalysis. (And actually, even then we might have just
> a more believable guess.)
Thank you. That is most clear.
I'll try to come up with a couple of actual PRNGs and do some
head-scratching on them. I think I'll start with a nice simple version
of rand() [1] and work my way up to algorithms such as the Twister very
slowly indeed. :-)
[1] You can put the crucifixes and garlic away, guys - it's just an
example...
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
From: [EMAIL PROTECTED] (Jorgen Hedlund)
Subject: Re: Software PRNG..
Date: Wed, 13 Dec 2000 18:45:59 GMT
On Wed, 13 Dec 2000 07:57:50 -0800, "John A. Malley"
<[EMAIL PROTECTED]> wrote:
>
>Richard Heathfield wrote:
>>
>> Jorgen Hedlund wrote:
>> >
>[snip]
>> >
>{snip}
>
>A biased random variable has a non-uniform probability density function.
>The probability that the random variable takes on a value between x_1
>and x_2 is just the integral of the area under the pdf between x_1 and
>x_2. The total area under the pdf, integrated from -infinity to +
>infinity, must equal 1. It's more likely for the random variable to take
>on some values than others when the pdf is non-uniformly distributed
>between -infinity and + infinity.
Oh my.. I don't believe I understood one bit of this. *sigh* .. Where
could I catch on this kind of theory?
What does 'pdf' mean in the above text .. (in my head, pdf is a file
format =)
BR/jh
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: STT stream cipher (update)
Date: Wed, 13 Dec 2000 11:38:48 -0700
Jorgen Hedlund wrote:
<snip>
> Anyhow, I also would like to know how public/private key
> ciphering works. As I've understood it, the private key
> must be uncomputable using the public key. And still it
> should be able to decipher.
<snip>
The first thing to realize is that the private key is
not really "uncomputable" from the public key; it's just
that (so far as we know so far) computing it takes way
too much work. So it is "practically" uncomputable.
In the example of RSA, the public key includes the
product of two prime numbers. (The private key is
also derived from the prime numbers.) Without going
into why encryption and decryption actually work (it's
number theory), the security rests on the obvious fact
that it is easier to multiply two numbers together than
to see the product and compute what the two factors were.
Current knowledge of the algorithms to do factoring,
combined with assumptions about computing resources,
gives us estimates of how big the numbers must be for
secure use. (I said above that it is "obvious" that
factoring is harder than multiplication, but no one
actually *knows* exactly how hard it is. It might, in
the end, turn out to be easy enough that RSA becomes
unsafe at any size. Or maybe we'll figure out exactly
how hard it is, and have exact key sizes. Most expert
opinion now is to behave as if we know what we're
doing, with a fudge factor.)
JM
------------------------------
Date: Wed, 13 Dec 2000 18:41:34 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Newbie
John Myre wrote:
>
> Andre van Straaten wrote:
> <snip>
> > I have another method which is as secure as the OTP:
> > I just don't have secrets.
> > LOL
>
> ditto LOL.
>
> Although actually, your method could be said to be even
> *more* secure: it doesn't leak the (maximum possible)
> size of a secret.
Yes, it does. Andre just leaked that the maximum possible size of his
secrets is 0 bits.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: YAPRNG
Date: Wed, 13 Dec 2000 11:52:58 -0700
Richard Heathfield wrote:
<snip>
> ROT-13 twice, anyone? <g,d&r>
<snip>
LOL
Thank God I typed "nearly", eh?
JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Newbie
Date: Wed, 13 Dec 2000 11:53:57 -0700
Richard Heathfield wrote:
<snip>
> Yes, it does. Andre just leaked that the maximum possible size of his
> secrets is 0 bits.
<snip>
Oops.
JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Software PRNG..
Date: Wed, 13 Dec 2000 11:55:25 -0700
Jorgen Hedlund wrote:
<snip>
> What does 'pdf' mean in the above text .. (in my head, pdf is a file
> format =)
<snip>
>From earlier in the post, "probability density function".
JM
------------------------------
From: Emrul <[EMAIL PROTECTED]>
Crossposted-To: alt.security.PGP
Subject: Re: Security of Netscape Messenger PGP PlugIn
Date: Wed, 13 Dec 2000 19:32:45 +0000
I've asked this question in here before quite a while back but received
not reply... so since we're on the subject of open/closed source
software... I feel the need to ask some questions:
1. How can software companies who develop cryptographic software make
money if they open-source their work? One thought I had was that source
could be made available for peer review under some form of Non
Disclosure Agreement; what would you sci.crypt boys think about that?
2. Another option is that after making a series of free and secure
open-source software, they could make more advanced closed-source
versions which cost. Would you trust software like that?
3. They could use AdWare... however I've never personally liked that
form of software because not even a program's can always be sure what
the Advertising code is sending around the net... yes.. its unlikely to
be crypto keys.. but it could be something relating to a user's real
life identification details, which would be a very bad thing. What's the
feeling about AdWare in sci.crypt ?
4 We're planning to release two cryptographic products this year; at
the moment I'm planning to release source-code and program, free for
personal use. So far its the best idea I've had but I'd welcome any
other suggestions. Authors do need to strike a balance between user
trust and profitability.
More details of the two programs will follow when we're closer to
release :)
-Emrul
John Myre wrote:
> Johnny Bravo wrote:
> <snip>
> > Worst case scenario...
> <snip>
>
> I agree with your sentiments, but I thought I'd point out
> that things could be much worse. An unknown binary could
> do practically any evil thing you could imagine, beyond
> slightly weakening the encryption strength. (C.f. worms,
> viruses, etc. etc.)
>
> JM
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: STT stream cipher (update)
Date: Wed, 13 Dec 2000 11:49:05 -0800
Jorgen Hedlund wrote:
> > The simplest way to wrap your brain around it, IMO, is to realize that
> > the public key and the private key have some simple mathematical
> > relationship such that the private key tells you important things about
> > what the public key will do. For example, consider a case where the
> > public key is a number that is the product of two 300-digit prime
> > numbers. Given the public key, it would be very hard to figure out those
> > two prime numbers. Nevertheless, knowing what those two numbers are will
> > tell you important things about what the public key will do
> > mathematically.
> >
> > DS
>
> You mean that if the private key is these 2 primes,
> and the public key is, for instance, the product of
> these primes, it is computable (with the private key)
> how the public key has "modified" the plaintext?
Other way around. The public key would be the product of the two
primes. The private key would be the two primes. So you can't easily go
from the public key to the private key, but you can see how the private
key tells you something _about_ the public key.
> I mean, you can't decipher without knowing the key
> that ciphered the data, can you?
No, but the key that ciphered the data may not be enough to decipher it
if the enciphering process is irreversible. The hallmark of public key
ciphers is that their enciphering process is irreversible. The
deciphering process is not just the enciphering process run in reverse,
it's a different process entirely.
In public key ciphers, the key that ciphered the data is insufficient
to allow you to decipher it. You also have to know something about the
public key, and that extra something is kept private.
DS
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Software PRNG..
Date: Wed, 13 Dec 2000 11:54:09 -0800
Jorgen Hedlund wrote:
> Although, I've a question about this term "biased", what do you mean
> with that something is "biased"?
If RC4 were a perfect random number generator generating 8-bit random
numbers, a person who tried to guess the next random number would be
right one in 2^8 times. Unfortunately, RC4 is not a perfect random
number generator. It should produce exactly the byte twice in a row one
in 2^8 times, but insutead it does so about one in 2^24 times too often.
This has virtually no affect on the usefulness of RC4 if used for its
intended purpose, generating a stream of bytes to be XORed with a data
stream for encryption purposes. However, it does have an affect on the
usefulness of RC4 if used as a PRNG for applications that require a
'near-perfect' stream of random numbers that can pass statistical
examination.
(This is from memory, I may have the numbers slightly off)
DS
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: YAPRNG
Date: 13 Dec 2000 20:27:34 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
If you xor two linear keystream generators together,
the result is still linear. Any linear keystream generator
is trivially insecure (can be broken with linear algebra).
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Unguessable sequence of unique integers?
Date: Wed, 13 Dec 2000 20:52:23 GMT
Simon Johnson wrote:
> moc.qit@nahoj wrote:
> > 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.
[...]
> Clock an additive generator twice (with a 2^32 word length)
> if the first output is greater than 2^31 then the output is the second
> word, if the first output is less, dump both words and start again.
Using the additive generators I'm familiar with (for example
from Knuth's Seminumerical Algorithms section 3.2.2) that
would be a terrible method. Do you have some other source you
can cite?
Also, how do we know it will not repeat values? Knuth
presents additive generators with long periods, but that's not
the sufficient.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Protocol for computer go
Date: Wed, 13 Dec 2000 22:00:36 +0100
On the computer-go mailing list [1] there is ongoing debate
on how to design a realistic protocol for computer go.
>From a cryptographic standpoint, computer go a is two-player
board game without hidden information (like chess is), played
between computers according to the rules of go [2], and timed:
a player's clock runs while it is its turn to play, overtime
player loose [3].
The main interest of computer go is that programs are very
weak compared to human players.
The goals of a protocol could be stated as:
(a) detects cheating, that is a human player helping the program,
for example using covert input channels.
(b) allows using machines supplied by the competitor, without prior
inspection by a referee, including remote play by Internet.
(c) allows programs to adapt their strategy to the time left.
(d) allows programs to compute while their opponent does.
(e) puts reasonable constraints on the referee.
(f) puts reasonable constraints on the programmer, including
not disclosing the source at all, or how the program works,
not even to a referee.
(g) [if at all possible] do not even ask the programmer to give
a fully usable executable to the referee; it might however be
acceptable to assume the referee will not let the executable
be reverse engineered, if unavoidable.
(h) [if at all possible] allow to run a match between two machines
without requiring a third trusted referee machine, even if
dispute can then occur regarding overtime.
(i) [if possible] allow the program to learn and improve during
a tournament.
(j) [if possible] allow the program to adjust its strategy
according to results of a tournament.
(k) [if possible] make the referee unable to help cheating.
A promising technique is that before the tournament each participant
publish the cryptographic hash of an executable, running on one of a
few standard platforms (say Linux, Win32, MacOS), and able to REPLAY
games as the original program did, but on a machine trusted by the
referee. The replay program needs to be submitted to a referee only
in case of dispute, and of course is checked for the correct hash.
Given the same input (most basicaly the other program's move), the
replay program must play exactly like the original did.
Optionaly (this is not all that useful), the replay program may
require a digital signature of all the previous moves before
responding to an opponent. The signature must be publicly verifiable
ande without subliminal channel (such as an RSA signature with
deterministic padding). This makes the replay program useless
without reverse-engineering to remove this portection. If in
addition the programmer can check that the referee does not
reverse-engineer the executable, and destroys it after replay,
the programmer is assured no usable know-how leaks in the
replay process (the referee can not "mistakenly" probe the replay
program to check how it plays).
A serious problem comes from the real-time nature of computer-go:
the replay program will run on a different (possibly slower)
machine, and thus there is the problem to adjust overtime. It seems
acceptable to define an extended time limit for replayed games,
maybe 100 time as long, to allow for high-performance machines
and inefficiency of an implementation on the reference platform.
But worse, the behavior of a program depends a lot on the amount
of time it already used, and maybe to some degree on the amount of
time left to its opponent. And it seems hard to recreate this
information from a log without opening a side channel that can be
exploited.
A typical cheating strategy would be
- the game program display two moves: its best and second best
candidate; a human arbitrates between the two moves, and tells
the program; if the first move is chosen, the program performs
a few queries to the timer at 2 second interval, else at 3 second
interval; it then plays what the human player decided.
- the replay program finds the same two moves, and decides which
to play based on the result of queries to the emulated timer,
separated by a timing loop of about 2.5 second.
There are a few other problems, like allowing for random generators
in the programs, or deciding which program starts. They are easy
to solve using well known crypto techniques.
Any proposition solving the timing issue, or showing it is an
impossible task ?
Francois Grieu
[1] For information on the list, mailto:[EMAIL PROTECTED]
with in the BODY of the text (NOT subject) the three lines:
info computer-go
help
end
[2] Concise go rules at <http://www.cwi.nl/~tromp/go.html>
Various other rules at <http://home.snafu.de/jasiek/rules.html>
[3] There is often an agreed-upon time limit, plus 5 second
allowance for overtime players, allowing the endgame to be
played even when overtime.
------------------------------
From: "Harvey Rook" <[EMAIL PROTECTED]>
Subject: Re: Virtual memory security hole?
Date: Wed, 13 Dec 2000 13:07:42 -0800
"Paul Rubin" <[EMAIL PROTECTED]> wrote in message >
> Why would your memory get written to disk in a crash? I mean it
> might happen because of some bug, but your files might also get
> broadcast over the network because of some bug.
It is very common for OS's to dump a programs memory to the disk when the
program commits an access violation such as accessing a NULL pointer. The
dumped memory can be forwarded to the programmer for diagnoses. The UNIX
term is 'core dump' the Windows NT term is "crash dump"
> Suspending to disk is a function provided by OS extensions on some
> notebooks, I think. So any encryption is done by the OS. But
> I don't know of any OS's that actually encrypt when doing this.
>
> I have the not-especially-widely-shared opinion that stuff like
> partition encryption should be done at the device driver level,
> but that's just an engineering question, not a cryptographic one.
The whole issue of accessing the swap file, and memory dumps raises a number
of hard questions. Under what circumstances would your attacker be able to
read the swap file, yet not be able to place a keyboard bug (Either hardware
or software) on your system. A hole in your network security? A stolen
laptop?
------------------------------
** 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
******************************
