Cryptography-Digest Digest #392, Volume #12 Thu, 10 Aug 00 01:13:01 EDT
Contents:
Re: OTP using BBS generator? (David Hopwood)
Re: Not really random numbers (Anthony Stephen Szopa)
Re: Empathic encryption? ([EMAIL PROTECTED])
Re: Simple Cypher? (Anthony Stephen Szopa)
Re: OTP using BBS generator? (Terry Ritter)
Re: Physical RNG (Anthony Stephen Szopa)
----------------------------------------------------------------------------
Date: Thu, 10 Aug 2000 17:15:22 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: OTP using BBS generator?
=====BEGIN PGP SIGNED MESSAGE=====
Benjamin Goldberg wrote:
> Bryan Olson wrote:
> [snip]
> > No, in that post David Hopwood got it right:
> >
> > | it has been proven that short cycles happen with negligible
> > | probability, if the parameter sizes are such that factoring
> > | is hard
> >
> > > There is a remarkable lack of desire to address this known weakness,
> > > even though we know how to do that.
> >
> > I take a different view: I think showing the failure happens
> > with negligible probability is a perfectly valid way to
> > address the weakness.
>
> Suppose we have a block cipher with big keys. Further suppose that a
> small number of those keys give the identity transformation, and all
> other keys are VERY secure. Also, suppose that there's no known way to
> find those weak keys without doing a trial encryption, but a trial
> encryption is trivial. Weak keys have low probability, but when they
> occur, the system is wide open.
To be as generous as possible to your argument, let's assume that there
is a proof, under assumptions that are as reasonable as the intractability
of factoring, that there are no other significant weaknesses in the cipher
(if there is no such proof, then this example is clearly not comparable to
BBS).
If the probability of a weak key is low enough to be considered
negligable (the decision as to what is negligable is up to whoever is
applying the security proof), then such a system would be considered
secure in most probabilistic models of security, under the assumption
that keys are selected at random. The system is also secure in practice,
if keys are selected by a good RNG.
So, the conclusions derived from the security model match what we need
in the real world, as well as they can be expected to (and modulo the
possibility of attacks that fall outside most formal security models,
e.g. power analysis, fault analysis, etc.)
There is the issue that keys might not in practice be selected at random,
but that is something that in most cases can be analysed independently of
the cipher.
However, note that some constructions for hashes, etc. based on block
ciphers (e.g. Davies-Meyer), are secure only if very strong assumptions
are made about a cipher's key scheduling; they are insecure when used
with ciphers that have even fairly minor key scheduling weaknesses.
I tend to avoid these constructions entirely - I just don't trust that
the assumptions will be satisfied.
Another important caveat is that if you are put in the position of selecting
a cipher that will be used for a very large range of applications (AES is
an extreme example of this), then it would be a bad idea to select an
algorithm that had weak keys, however unlikely. This is because there's
no way to be sure that the random-key assumption will hold for all
applications that use the cipher.
> With BBS, short cycles occur with low probability, and the system is
> very secure when we don't have a short cycle. There's no known way to
> detect weather short cycles will occur without explicit testing, but
> explicit testing is trivial. If a short cycle does occur, the system is
> wide open.
>
> Does anyone see a similarity?
Yes, of course; they are quite similar cases (with the caveats mentioned
above, and the one below about the cost of testing for weakness).
> Would anyone use the described block cipher without testing for the
> identity transformation? Assume that the identity transformation occurs
> as often as short BBS cycles.
I would, if I was confident that the weak keys weren't a symptom of some
other hidden weakness. If I wasn't confident of that, I probably wouldn't
use the cipher at all.
A practical example is IDEA: this has a set of weak keys that occur with
probability about 2^-96. As it happens I haven't written any applications
for end-users that use IDEA, but if I did, I wouldn't consider it
necessary to check for weak keys.
OTOH, note that testing for an identity permutation is much cheaper and
less complex than testing for short BBS cycles, so it would also be a
reasonable and consistent position to argue for testing in that case, but
against testing cycle length in BBS.
> Personally, I think there exists some kind of further restriction on the
> parameters to BBS which will [provably] eliminate short cycles entirely,
> but we haven't found it yet.
I think that's unlikely, because I can't see any approach to proving the
open question mentioned below. Given that it's 18 years since the BBS
paper was published, probably one of the following is true:
- not many people have looked at this question (which I doubt given the
amount of research into bit-security of IFP-based cryptosystems),
- there is a published proof that I'm not aware of,
- it is difficult to prove,
- it is false.
[snip]
> > [Klaus Pommerening]:
> > > | >Is there any known result that some choice of parameters in BBS
> > > | >guarantees that the LSBs don't give short cycles?
> > [Ritter:]
> > > |Not that I know of. I never even thought of investigating such a
> > > |thing on my small models. I guess I assumed that sort of thing
> > > |was exactly what the proofs guaranteed.
> >
> > Yes, exactly the kind of thing I've pointed out both before
> > and after that post: the long cycle filter doesn't imply
> > there's no case in which particular parameters fail (though I
> > don't know if this kind of failure is possible). But why,
> > after reading the paper, citing the paper, and accusing
> > everyone else of not reading the whole paper, were you still
> > _assuming_ what the proofs guaranteed?
>
> What it seems that Ritter is saying is that he's assuming that if there
> are no short cycles in the state then there will be [no??] short cycles
> in the LSB of the state.
Well, the BBS paper is quite clear about what the state of public knowledge
on this was in 1982 - it's posed as an open question just after Theorem 10
(and AFAIK it is still an open question).
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOZLTZTkCAxeYt5gVAQGxJAgAuLCoUTitQOxGAJzK76iBt03jqUI7XLN1
iyDwV2zgLDSBZ97cgHo4R/lR9vGi6FhvLx5olkixYRg9s1JHt/dJOG38yzHdiOc7
0R4IMOcFZXpENtevDBoJEUTm3+9stGK30ablyeXRj8IuSFeGO0goAXK6FqKlt4jK
MYDfiJ/KY59yq8vCLe9wMTv5erP6fA3KWUcCX2no7O5DwUeL25YbaTzqpzzoYKLo
aF1P+h6ak7Ve6DB/69awjMTTx9dGr78Mi5T9oB6udgGyFfDFdCAotJ9qgbG3oac1
CX6cj4kuurIPzJMLzYCvOIIs0vejPVCWf+gkqLqH39G6+FmFV+kPcA==
=cVB+
=====END PGP SIGNATURE=====
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Subject: Re: Not really random numbers
Date: Wed, 09 Aug 2000 21:48:49 -0700
Jamie wrote:
>
> In the UK pre-Pay phone cards are big business... you buy a card, reveal a
> number, key the number to a phone system and you have so much talk time. I
> am working on an application in a simmilar field...and ofcourse the issue of
> generating these numbers has come up once again. I need ideas for a number
> generator that satisfy the following contidions:
>
> 1 The magnitude of the generated numbers can be specified, 2^30, 2^35,
> 2^40... 2^90
>
> 2 The period must be greater then 2^^20
> (So numbers generated dont repeat)
>
> 3a Given a short fragment of the sequence it must be difficult to deduce the
> next number in sequence
> 3b Given one number it must be unlikely that another number is both close in
> value and close in position in the sequence
> (vague but I guess I mean that a "hacker" wont succed randomly guessing the
> next number)
>
> 4 The sequence must be re-startable.
>
> 5 No need for an even distribution or anything like that.
>
> My starting point was an algorithm like
>
> Nn+1=(P1*Nn+P2) mod P3
>
> P1,2,3 are primes P3 determining the magnitude of the numbers generated
>
> Nn+1 the next number in the sequence
>
> But this seems to be full of holes.
>
> any ideas on an algo ?
Go to http://www.ciphile.com and download OAR-L3: Original
Absolutely Random - Level3 random number generator shareware
software.
Go to the Downloads Currently Available web page and download the
software directly. You will be able to generate more random numbers
than you could conceivably ever need.
If used according to recommendations there is practicably no chance
anyone will be able to duplicate your random numbers.
If you think you could use this software commercially, email me.
A.S.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Empathic encryption?
Date: Thu, 10 Aug 2000 04:54:57 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> I can think of one kind of [bizarre?] stenography for sending
> information to a musician. Start with music which has been generated
by
> a computer following various rules of composition... so it will be a
> good, well formed, though probably unimaginative piece of music.
Then,
> every nth note, change that note so that it is, to a professional
> musician, obviously not right, and where, hopefully, the note that
> *should* be there, is also obvious. The difference between the note
> that *is*, and the note that *should be* is one nibble of data.
Print
> the data as sheet music, and send it in the mail. Or even send it by
> email, as a midi... It would, after all, be a valid midi; Of
course,
> you'd have to be a musical genious to be able to decode it by just
> listening to it.
>
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Subject: Re: Simple Cypher?
Date: Wed, 09 Aug 2000 21:53:53 -0700
Jamie wrote:
>
> Thank you all for your comments. I'm prehaps not as much of a newbie as some
> seem to think, I forgot to say in my origional post that there were no fixed
> format headers etc to the message, and of course messages would be prefixed
> with a short block of random data (ok fixed len but all that's needed for
> this app). Again the messages will be <1000 chars (not words .. so no
> dictionary attacks) sender details are known outside of the message contents
> and because it is a closed system the "public" keys are secret out side of
> the system. So the whole symetric key generation and signing process seems
> over kill.
>
> Finnaly the bit I'd really like help with is "where can i buy a simple
> library to let me do this cyphering?"
>
> Thankyou for any help you can give me
>
> Jamie
>
> "Jamie" <[EMAIL PROTECTED]> wrote in message
> news:8moha6$hqp$[EMAIL PROTECTED]...
> > Can anyone help?
> >
> > As part of a computer application I am developing I need to be able to
> > securly send and receive messages over an insecure medium...the web...
> > nothing new there. These messages will be short < 1000 characters. I must
> be
> > able to verify the sender of the message, and ensure that only I can
> decrypt
> > messages sent to me....still nothing new. I dont need to be able to verify
> > the content of the message. I trust the message sender not to dispute the
> > message contents...Makes things a bit easier prehaps. A number of
> > predetermined trusted people may send messages to me, and I in turn send a
> > reply back to the sender. There is no need for any other lines of
> > communication. I had initially thought that a simple public/private key
> > cyper system would be ideal. I would generate a key pair and distribute
> my
> > public key to each of the message initiators through a verifyable
> mechanism.
> > Each message initiator would also generate a key pair and notify me of
> their
> > public key in a verifyable manner. Then each message could be encoded
> first
> > with their private key then my public key. The message would not be
> readable
> > in transit as only I could decode it with my private key, and I would be
> > asssured that the supposed sender was genuine by decoding again with their
> > public key.
> >
> > When I started looking around for software (to buy) that would accomplish
> > this (simple?) task I couldn't find anything. All the software I can see
> > solves the much more generalised (and complex) problems of secure
> > communications and brings up Public Key Infrastructures, digital
> signatures,
> > certificate revocations.... the full works.... which I dont need for this
> > project. I understand that an all singing and dancing system would work
> for
> > me, but it seems such a waste of effort to implement somthing that
> delivers
> > so much more than I require.
> >
> > Can anyone point me in the right direction for software that meets my
> simple
> > needs? Or am I being too naive thinking the scenario outlined above is
> > sufficent and I sould be thinking of going the "whole way".... The "value"
> > of the messages being exchanged isnt very high and only enough security is
> > needed to disuade the casual observer (12year old kid) from wasting too
> much
> > time trying to "hack".
> >
> > Thank you
> >
> > Jamie
> >
> >
Go to http://www.ciphile.com and get your shareware copy of OAP-L3:
Original Absolute Privacy - Level3 encryption software package.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: OTP using BBS generator?
Date: Thu, 10 Aug 2000 05:07:21 GMT
On 9 Aug 2000 21:20:03 -0000, in
<[EMAIL PROTECTED]>, in sci.crypt lcs Mixmaster
Remailer <[EMAIL PROTECTED]> wrote:
>Terry Ritter writes:
>> The LSB of the x^2 mod N result *is* the output of BB&S. If a cycle
>> of LSB's could be shorter than the cycle itself, BB&S would be
>> seriously damaged. To the extent that there is a proof of BB&S, that
>> proof must cover this situation, because this *is* BB&S.
>
>This is correct. It is frustrating that you have come so close here to
>understanding the position of those who have been arguing against you
>for so many years.
On the contrary, I think I understand that position well, while you
clearly have serious problems understanding mine:
The very fact that you are willing to trust a "proof" which overlooks
a known and demonstrated (if infrequent) weakness, leads me to believe
that we do not have the same understanding of what "proven secure"
should mean in cryptography.
I DO NOT ACCEPT that a cryptosystem which has a known potential
weakness can legitimately be called "proven secure."
>You need only expand your argument to say, that if a cycle of outputs were
>short enough to be found in practice, BB&S would be seriously damaged.
>And then, as you say, "To the extent that there is a proof of BB&S,
>that proof must cover this situation, because this *is* BB&S."
False. We are not interested in the case of an opponent trying to
break the system by finding short cycles. That is indeed unlikely to
be successful. Instead, the situation of interest occurs *after* a
short cycle has been selected for use. When a short cycle is been
selected, the system may be insecure, despite claims of a mathematical
proof of strength. That is a contradiction.
>From my point of view, the whole reason for a proof is to absolutely
guarantee something. The sort of proof we have been discussing simply
does not do that, presumably because it is not really the same sort of
"proof" that students learn in algebra. I assume that what we really
have is a *statistical* proof, which is *not* just a different form of
proof and just as good, but instead a *lesser* *standard* of proof.
With a statistical approach, we might prove that something "almost
always works." That's a fine goal; I have no problem with that sort
of proof. My problem is with implying that "proven almost always
secure" means "proven secure." It does not. A far better description
would be "a statistical proof of security."
And we have yet another problem: How can we believe that the short
cycle insecurity is the *only* one which this proof allows to exist?
We *can* prevent the short-cycle insecurity, because we know about it.
But we *can't* prevent other security problems about which we know
nothing.
>The point being, that if anyone could feasibly find short cycles when
>using intractably large RSA moduli (other than trivial cases like x=1 or
>-1), that would invalidate the BB&S proofs. But by the proof, we know
>that this is impossible (assuming that quadratic reciduosity is hard,
>which virtually everyone agrees with). (Actually, previous discussions
>on sci.crypt have shown that short cycles are infeasible to find even
>assuming the factoring problem, which everyone who uses RSA agrees
>is intractable.)
For the purposes of this discussion, I believe we have all accepted
factoring security. More generally, I am less confident.
>One other point, because it keeps coming up. The toy example of 1081 =
>23*47 is meaningless in evaluating the *tractability* of finding short
>cycles.
Of course.
>Factoring 1081 is trivial. Hence the proof which reduces
>finding cycles to factoring will not apply, because factoring a number
>of this size is not difficult. You might as well try to evaluate the
>security of AES by cutting it down to something with a 10 bit key.
Tiny versions of any scalable cipher are generally not secure, so one
might ask, "What good are they?" Well, tiny versions provide valid
insight into the structure of a complex system at a size that humans
can approach. Such a system actually can be measured and analyzed
experimentally, to either verify or refute assertions made from theory
alone.
Many comments here have pointed out how difficult it is to find short
cycles. If all we had to experiment with was a full-size BB&S system,
we might not even *know* about short cycles. Yet a tiny version of
BB&S exposes this structure in an irrefutable way. In fact, a tiny
version of a scalable cipher can support an exhaustive experimental
analysis which is actually *impossible* on the full-size system.
In this context, 1081 is neither trivial nor meaningless. Instead, it
is a way for us to see the structure of a valid BB&S system at a size
which humans can investigate. Since we build the large system from
exactly the same formula as the small one, we expect to find inherent
structural similarities, and we do.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Subject: Re: Physical RNG
Date: Wed, 09 Aug 2000 22:00:07 -0700
Ed wrote:
>
> Hello,
>
> I'm searching for a physical random number generator.
> But I've have important constraint :
> - it should be plugged in a PCI bus
> - it should be useable under Solaris system ( or Unix system)
>
> If you know a physical RNG that don't match these criteria,
> it could help me.
>
> Please send any information to : [EMAIL PROTECTED]
>
> Edouard DESSIOUX
> Everbee
You obviously want to generate random numbers.
You cannot do any better than:
Go to http://www.ciphile.com and download a shareware copy of
OAR-L3: Original Absolutely Random - Level3 random number
generator software.
Go to the Downloads Currently Available web page.
Or you can get OAP-L3: Original Absolute Privacy - Level3 encryption
software package shareware.
You should check this software out.
A.S.
------------------------------
** 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
******************************
