Cryptography-Digest Digest #83, Volume #12 Thu, 22 Jun 00 07:13:01 EDT
Contents:
Re: Encryption on missing hard-drives (Paul Rubin)
Re: Encryption on missing hard-drives (Mok-Kong Shen)
Re: Weight of Digital Signatures (Mok-Kong Shen)
Re: small subgroups in Blum Blum Shub (Mark Wooding)
Re: Missing Info in the crypto-gram of MR BS (Tim Tyler)
Re: Length of pseudo random digits (Tim Tyler)
Re: Variability of chaining modes of block ciphers (Mark Wooding)
Re: Variability of chaining modes of block ciphers (Mark Wooding)
Re: Quick Question on Primitive Elements GF(p) (Tim Tyler)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Encryption on missing hard-drives
Date: 22 Jun 2000 08:11:03 GMT
In article <Gy945.14$[EMAIL PROTECTED]>,
<[EMAIL PROTECTED]> wrote:
>On a more sci.crypt note, noone's answered my original question which
>is if it's possible to encrypt a device such that it's impossible to
>read the contents without leaving a trail. Something similar to a one
>time password system, where a series of keys must be used or some
>other clever algorithm. Just for fun, we'll allow a secure connection
>to a trusted party.
Sure, of course. Just put the contents on a server at the trusted
party and have the trusted party log all accesses.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Encryption on missing hard-drives
Date: Thu, 22 Jun 2000 11:01:10 +0200
[EMAIL PROTECTED] wrote:
> ABC news reported today that "[Bill] Richardson said he has changed
> the procedure which now requires information such as the data on the
> hard drives to be encrypted" which strongly implies that it
> wasn't. Really though, no amount of encryption is going to help in the
> face of abysmal physical security. Twenty six people were allowed
> unescorted access to the vault, and could remove items without signing
> for them. On top of that, the last inventory was for the y2k
> inspection.
Judged with commonsense, one can conclude that the materials involved
(despite the official claims) could not be very critical. I base my
conjecture
on a case I know: In the seventies a friend developed a program for a
certain hightech firm. The program was on a magnetic tape and kept in a
vault. Each time when the program got run, the tape was taken from the
vault to the computing centre and put back after the run, always under
the supervision/protection of an armed guard. Even years after leaving
the firm, he was requested to provide informations about the names of
countries he visited during vacations. So it seems unbelievable that the
present hard-drive could contain materials that are really any precious.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Weight of Digital Signatures
Date: Thu, 22 Jun 2000 11:00:56 +0200
John Savard wrote:
> The difficulty with digital cash is if it is to be anonymous, or if it
> is to be able to be processed off-line. Otherwise, there is no
> problem, which is why we already have credit cards.
Do you consider what is done with telephone cards an on-line or
off-line processing?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: small subgroups in Blum Blum Shub
Date: 22 Jun 2000 09:50:47 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
> in sci.crypt [EMAIL PROTECTED] (Mark Wooding) wrote:
>
> >In the particular case under discussion, the assumption X is that our
> >adversary cannot factor a given BBS modulus, and the consequence is that
> >the BBS generator with that modulus is unpredictable by that adversary.
>
> As a non-specialist, that sounds to me like a very coarse and
> broad-stroked approach. Indeed, the idea of starting out by assuming
> our ultimate goal sounds quite dangerous to the forming of correct
> logical conclusions. In fact, it sounds almost circular.
Where did I start with the ultimate goal?
The Integer Factoring Problem, and its close relatives the Quadratic
Residuosity Problem and the Square Root Problem, are well known
reference problems in public-key cryptography. We don't have proofs
that any particular reference problem is actually difficult, but, like
the various Discrete Logarithm Problems, they're about as good as we can
get right now.
The demonstration I alluded to above is that, *given* the difficulty of
IFP (or, actually QRP), we can produce a random number generator whose
output is unpredictable. Or, more precisely, if n is a Blum integer,
and A is an adversary unable to factor n, then the BBS generator mod n
is unpredictable by A.
The *premise* is the difficulty of our reference problem, i.e., that
factoring is `too hard' for our adversary. The *goal* is to produce a
random number generator with unpredictable output.
> One problem is that such a proof tends to gloss over nasty facts with
> no indication of their existence. There is no hint that short cycles
> exist. Even though finding a short cycle would violate the
> fundamental assumption, there is no sub-assumption which would prevent
> one from finding the short cycles which do in fact exist. So finding
> short cycles will happen.
That's the point: there doesn't need to be a `sub-assumption'. See
where I get frustrated enough to blow some dust off my symbolic logic
below... ;-)
> While "improbable" means "almost never," it also means "must occur
> sometime." As soon as we introduce probability we must allow for
> every *possibility* to occur. So even though it is *improbable* to
> select a short cycle, that *must* occur, sometime. But that allows
> factoring N, and for some reason we don't get: "Oh, the assumption
> must be false."
There's a subtle difference between an assumption and a hypothesis. In
this case, we are hypothesizing the difficulty of the reference Integer
Factoring Problem. If we then assume that the adversary can find a
short cycle, we find that he can factor, the hypothesis being thereby
contradicted. The hypothesis stands and the assumption fails; thus, we
conclude that the adversary cannot find short cycles. We keep our
hypothesis because it's reasonable: we don't actually have a good way of
factoring.
> One might well think that the whole point of proofs based on
> assumption is that we can develop implications of the assumption, and
> then if the implications are shown false, the assumption also must be
> false, end of story. But here we have, "Oh, no, the facts must be
> wrong because if the assumption is false the sky will fall." As a
> non-mathematician, it sounds to me like we have stepped outside of
> mathematics. I think we have shown the assumption false, or at least
> that it does not hold unconditionally, as stated.
OK, I'll try a slightly different approach. Let F_A(n) be the statement
that A can factor n, and let C_A(n) be the statement that A can find
cycles in the BBS generator mod n. We have shown that if A can find a
cycle, he can factor. We can write that as C_A(n) => F_A(n). This is
equivalent to saying that !F_A(n) => !C_A(n) -- I can trundle through
the formal proof, but it's not very interesting. Now, our initial
hypothesis is that factoring is hard; i.e., !F_A(n). You can tell me
the conclusion.
> >There is a technique common in mathematics named `reductio ad
> >absurdum', or `proof by contradiction', where one assumes the converse
> >of what is intended to be proven, and deduces a result which contradicts
> >its hypothesis.
> >
> >We can apply this technique to the current situation. Consider a Blum
> >integer n, and an adversary A who is unable to factor n. Then A cannot
> >find a cycle in the output of the BBS generator. We prove this by
> >contradiction by demonstrating that, if A finds a cycle, he can factor
> >n. Since the base we're working on states that A can't factor n,
> >something must have gone wrong. The only thing which might be wrong is
> >the assumption that A could find a short cycle. The result follows.
>
> That sounds wrong to me. You claim to have proven that short cycles
> cannot "be found," but I think you have proven that short cycles
> cannot exist, which is clearly false.
No. It's obvious that cycles exist, since the quadratic residues mod n
are a finite set and the mapping x |-> x^2 is a permutation. (I've
proved this fact in a separate article; it would be silly to deny it.)
However, our adversary, who isn't `allowed' to be able to factor the
modulus, can't find any. (Note that, actually, it's not just short
cycles he's not able to find: it's *any cycle at all*.)
> If short cycles exist, they will be used, albeit with low probability,
> unless that is prevented. But even a low probability of use is still
> use. Short cycles will be used and when they are that will allow
> factoring N. Since the assumption disallows that, the assumption is
> false.
Intriguingly, I think we're actually looking at the BBS generator from
different starting points. You're looking at it from the standpoint of
a single user who's just generating random bits for some reason. I'm
looking at it from the angle of the Blum-Goldwasser public-key
cryptosystem, where the modulus is *public*. From my point of view, it
doesn't matter if we actually *use* a short cycle, just whether an
adversary can find one, given the modulus on a silver platter. But I'm
happy that the security of the system rests on the difficulty of the
QRP.
Of course, when we use the BG system, the starting seed must be chosen
by a user who doesn't know the factors of n, and can't carefully pick
`good' seeds. This doesn't matter: BG is still strong, except against a
chosen ciphertext attack.
> And since very, very unlikely is *not* the same as impossible, I want
> to know where the explicit assumption is that made that so. Unless an
> assumption is explicit, we have no chance to decide whether it is
> really something we want to assume. And I do not.
The explicit assumption, and it really is very explicit, is that the
Integer Factoring Problem, is too difficult for an adversary. That's
all we need. We really do have a solid proof that predicting a BBS
generator is as hard as factoring.
-- [mdw]
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Missing Info in the crypto-gram of MR BS
Reply-To: [EMAIL PROTECTED]
Date: Thu, 22 Jun 2000 09:09:51 GMT
James Felling <[EMAIL PROTECTED]> wrote:
: I will state that I feel that in all likelyhood there is a "recognisability"
: factor that a compression algorithim posseses. Similarly there is a
: "recognisability" factor that any type of input may have. I believe that if
: the compression is more easily recognised than the input then do NOT
: compress, as you make the situation worse. If that is not the case, you will
: make the situation no worse than it previously was.( assuming that your
: compression either shrinks or leaves the file size equal)
While I largely agree with this, there's enough present for me to want to
pick at.
Firstly, if the plaintext is recognisable, it does /not/ follow that the
result of arbitrary decompressions is recognisable.
The counterexample is where practically all decompressions result in
plausible looking target text.
My usual example of this involves compression using message numbering.
I.e. 0 -> "All clear on the western front"
1 -> "It rains on the plains of Spain"
2 -> "Send more troops" ... etc.
Such a "compressor" can retain a bijection between the set of all possible
messages and the resulting compressed files, by an expanding encoding
scheme used for unrecognised inputs, if this is considered desirable.
Here, valid plaintext messages are normally easily distinguished from
random files. They are (after all) ASCII text. However, for most messages
decrypting with the wrong key will result in a message that decompresses
to something very plausible looking :-(
How "easy" the original message plaintext is to recognise is not
relevant. Whether this is ASCII text or not doesn't come into it.
What matters is how easy it is to identify a correct decrypt
form the encryption component - i.e. how easy it is to distinguish
a genuine compressed message from some random garbage.
The other problem I noticed was in the idea that if it is easier to
recognise the plaintext than the compression method, using an identifiable
compression method will not make things worse.
To my ears this sounds like the idea that if it's generally easier to spot
spies based on their accent, than by checking their employment references,
you shouldn't bother with getting their faked references straight.
One problem is that sometimes use of methods to recognise the plaintext
do not uniquely identify the correct plaintext.
In such a case, the availability of *additional* halting criteria can help
extract the correct meaning from the cyphertext.
Another problem is that different halting criteria may be useful in
different circumstances.
Say there's problem (caused by a bug) that allows the last half of each
block to be successfully decrypted - while the first half remains unknown.
Here decompressing is likely to be impossible; since there are a
stupendous number of possible decompressed files.
However, imagine the case of a non 1-1 compressor which uses each 32nd
bit as a CRC check.
Under such circumstances it will be much easier to check for the
signature of a poor compression method than to check for plaintext,
even if checking for the plaintext is normally very easy.
In short, you can't normally make a blanket statement that one halting
criteria is harder to use than the other. Thay may be of differing
utility under different circumstances.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Length of pseudo random digits
Reply-To: [EMAIL PROTECTED]
Date: Thu, 22 Jun 2000 09:22:52 GMT
Jacques Th�riault <[EMAIL PROTECTED]> wrote:
: How can I calculate the period of a random digit generator.
: Is there any formula to estimate such a period?
Here are a couple of approaches:
1) Test the output to see if it is periodic. Depending on your
application, you may need to do this with more than one possible seed.
Typically this only lets you conclude with certainty that a cycle
doesn't exist. You can't conclude with certainty that there's
definitely a cycle from any finite volume of output - since (e.g.)
"...10101010101..." may be part of a genuinely random sequence.
2) Examine the algorithm and its documentation in an attempt to
demonstrate using mathematical proofs that cycles no shorter than a
given length exist.
If your random digit generator is deterministic - i.e it's a PRNG, rather
than an attempt at an RNG - you can place an upper bound on the possible
period by examining the size of the generator's internal state.
There are a couple of common cases worth mentioning:
If your generator is reversible, and each state has a random but unique
precursor, there a formula to give the expected period.
If your generator simulates a random map between states, there's another
formula to give the expected period.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Legalise IT.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Variability of chaining modes of block ciphers
Date: 22 Jun 2000 10:00:06 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> It is not seldom the case that one's favourite good cipher has a fixed
> key size and hence that slight longer-ness isn't available,
> unfortunately. Variability of key size is a design virtue in my
> humble view but appears to be rather difficult to realize well in
> certain types of encryption algorithms.
How strange. I've seen very few recent ciphers which have fixed-length
key sizes. I suppose that the CAST ciphers are a case in point, but I
also suspect that CAST-128 is `good enough' without playing silly games
with chaining modes. All of the AES entries support keys at least as
large as 256 bits, which is `more than enough'; MARS and RC6 are notable
in allowing much longer keys. Blowfish, RC4, and RC5 all support
`sufficiently[1] large keys'. Bolting the Rijndael key schedule into
Square would increase key size to `more than enough' (but I suspect that
the Counterpane team's analysis of Rijndael has demolished Square along
the way, so it wouldn't be worth it). SEAL's key is fixed at 160 bits,
which is a bit of a shame, although a variant based on (say) Tiger
rather than SHA1 would easily increase this.
Finally, if your `favourite' cipher doesn't have a large enough
keyspace, that's a good reason for picking a different `favourite'.
May I recommend Blowfish? ;-)
[1] In the Rolls-Royce sense.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Variability of chaining modes of block ciphers
Date: 22 Jun 2000 10:01:43 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> If you believe that your cipher is really strong enough, then you of
> course don't need to consider anything extra. ECB is then presumably
> already o.k.
No. ECB has weaknesses (block rearrangement and copying) which apply
even with an ideal block cipher.
-- [mdw]
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Quick Question on Primitive Elements GF(p)
Reply-To: [EMAIL PROTECTED]
Date: Thu, 22 Jun 2000 09:33:43 GMT
Simon Johnson <[EMAIL PROTECTED]> wrote:
: Is the definition of a number that is a primitve element GF(p),
: if you can mutliply it by itself over and over, and get every
: value 0.....p-1?
No. One - not zero. Consider what would happen if x * x * x * x ... was
ever equal to zero. All subsequent elements would be zero :-(
x being primitive with respect to p often leads to x being called
a "generator" in GF(p).
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
** 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
******************************
