Cryptography-Digest Digest #448, Volume #12 Tue, 15 Aug 00 09:13:01 EDT
Contents:
Re: OTP using BBS generator? (Mark Wooding)
Re: Crypto Related Professional Attitude (Mark Wooding)
Re: Crypto Related Professional Attitude (Mark Wooding)
Re: Crypto Related Professional Attitude (Mark Wooding)
Re: Proposal of drafting rules of conduct of posting (Mark Currie)
Re: OTP using BBS generator? (Mark Wooding)
Re: New William Friedman Crypto Patent (filed in 1933) (John Savard)
Re: OTP using BBS generator? (John Savard)
Re: Looking for password statistical data (Mok-Kong Shen)
Re: Crypto Related Professional Attitude (Mok-Kong Shen)
Re: OTP using BBS generator? (Mok-Kong Shen)
Re: Crypto Related Professional Attitude (Mok-Kong Shen)
Re: Impossible Differentials of TC5 (tomstd)
Re: Big Brother Is Reading Your E-Mail (tomstd)
Re: OTP using BBS generator? (John Savard)
Re: What is up with Intel? (Jonathan Thornburg)
Re: Looking for password statistical data (Anders Thulin)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: OTP using BBS generator?
Date: 15 Aug 2000 11:13:08 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> So we know the size of these. But what useful implications do they
> have in this context (i.e. concerning 'difficulty'), if these are not
> otherwise made definite/clear? BTW, do we have sort of 'meter' for
> rigorously quantifying that 'difficulty'? Thanks.
No. I left my description deliberately vague. Our understanding of
what numbers are particularly hard to factor will change as we get
better at factoring, and it will change in an unpredictable way.
Currently, our best general-ish factoring method takes time related only
to the size of the number being factored. So we just choose `big'
numbers. This might change.
It might not.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Crypto Related Professional Attitude
Date: 15 Aug 2000 11:46:23 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> This post is for the professionals such as Biham, Rivest,
> Schneier, Wagner, Shamir, Coppersmith, etc...
>
> Why don't you guys ever participate even a little in sci.crypt?
I had the impression that David Wagner *does* participate, rather a lot,
in sci.crypt[1]. Bruce Schneier also pokes his head in occasionally,
and I've seen occasional articles from Vincent Rijmen, Lars Knudsen,
Jean-Jacques Quisquater and others.
[1] Of course, it might have been an imposter, but if all imposters are
that helpful and intelligent then I think we could do with more of
them.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Crypto Related Professional Attitude
Date: 15 Aug 2000 11:53:46 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> Safuat Hamdy wrote:
> > I doubt that one can seriously learn anything in sci.crypt.
Oh, I learn new things all the time. Even the really bad `can't
possibly be insecure' fake one-time-pads sometimes throw up interesting
snippets of analysis. I often get pointers to interesting papers as a
result of threads here. And Bill Unruh's recent question about modified
CHAP has led a friend and me towards a rather interesting key-exchange/
identification protocol, which I'm trying to analyse in spare moments.
> It depends on how much one already knows. In fact I've obtained a
> couple of useful leads here (from the semi-pros), although it would
> probably have been more efficiently done via sci.crypt.research.
My impression is that sci.crypt.research is moribund. I see very little
there apart from the regular FAQ.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Crypto Related Professional Attitude
Date: 15 Aug 2000 11:59:23 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> Also why don't those dudes post here to discuss their findings?
> Instead they just plug their work once and a while. Wow they SPAM
> this group that's nice.
I'd hardly say that it's SPAM. It's certainly on-topic -- it's
cryptographic research, after all, and we *are* meant to be doing
cryptography here, I think -- and, to my mind, extremely interesting.
More please!
-- [mdw]
------------------------------
Subject: Re: Proposal of drafting rules of conduct of posting
From: [EMAIL PROTECTED] (Mark Currie)
Date: 15 Aug 2000 12:00:31 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>wtshaw wrote:
>> I wonder more if no one points out some glaring problem. Let me give a
>> good example: I was overly excited about some prospective ciphers lately,
>> products of latenight magical thinking. Breaking my own rules, it has
>> happened before, I posted without thinking sufficiently and actually
>> making algorithms work. So, I confess, Lattice and Sinnet at best are
>> hashes, be it suggestive of a whole family of them. The ciphers are not
>> invertable at all, maybe should be not even be called ciphers.
>>
>> Why did no one catch this? My face is red. I screwed up. I had
>> extensive communication directed at my own shaddow, and lack of response
>> should not have been taken as anything positive. I accept my being human,
>> and everyone else being that way too; we all like to never make mistakes,
>> never get a bit too zealous, or post in an less that productive manner.
>
>Thus you see that, if the noise level is too high, your
>voice isn't likely to be heard. It should perhaps be
>explicitly pointed out that it seems that most feedback
>in out group is of negative nature, seldom of positive
>nature. In other words, one barely sees approvals or
>agreements. Consequently, if one doesn't get follow-ups,
>one doesn't know what one writes is o.k. or not and is
>so to say left in the dark.
>
One advantage of harsh criticism is that it can limit noise. It makes you think
a bit before posting. I have been taken out before for posting something that
hasn't been thought through properly. As long as it doesn't get too retorical,
it can serve a purpose. I disagree with pure negative feedback though. I think
that if you take someone out, you should at least offer a constructive
alternative to their claim.
Information security is a fairly wide discipline and it is difficult to be an
expert in all areas. Therefore poster's should not feel too bad when they are
legitimately chastised. Readers also should note this and not be too quick to
relegate a chastised poster to the ranks of useless novice, since the person in
question may be an expert in other areas of crypto and may offer useful
information in other dialogs.
I do agree with you about the lack of approvals. Unfortunately a simple "yes I
agree" could be viewed by some to be noise since in most cases it really only
benefits the original poster.
Mark
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: OTP using BBS generator?
Date: 15 Aug 2000 12:16:43 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> (1) Does BBS give any result of the (frequency) distribution
> of the cycle lengths of LSB sequences so that one can have
> a 'concrete' feeling of how likely one gets a long/short
> cycle? (BTW, how much is exactly 'long' or 'short', in
> relation to p, q or n?)
Not that I recall.
> (2) David Hopwood pointed out that the BBS article left open
> the question of the relationship between the cylce lengths
> of LSB and the cycle lengths of the direct output of the
> congruence relation. Does this theory 'gap' have any effect
> on the proof of the unpredictability of the LSB sequences?
> If not, what's the (global/rough) reason? (Note that a
> cycle length of 1 or 2 of LSB would certainly be actually
> predictable.)
No. The proof of unpredictability is a two-step thing:
* firstly, it shows that, if you can predict a BBS generator with
probability 1/2 + \epsilon then you can also decide quadratic
residuosity with probability 1/2 + \epsilon;
* and secondly, it gives a simple algorithm for `amplifying' advantage
in deciding quadratic residuosity so that small biases can be used
to efficiently solve QRP completely, in expected polynomial time.
> (3) Does the 'check' being disputed really prevent a certian
> lower bound of the cycle lengths of the LSB sequences
> (not the direct output of the congruence relation) of
> being inadvertently 'under-run' or does the check only
> do that in a probabilistic sense (i.e. with certain
> probability not equal to 1)? What is that lower bound
> actually (in relation to p and q)?
It doesn't do anything of the kind.
> (4) Does the mathematics of BBS really gaurantee that there
> is absolutely no bias or serial correlations etc. in
> the LSB sequences? Has that been explicitly proven in
> the BBS article? (Note that it is inconceivable that
> any 'other' PRNG that has statistical defects qualifies
> for use in secure crypto applications. So I believe
> that BBS must somehow show that the LSB sequences are
> statistically impeacable.)
It shows that BBS output is indistinguishable from random data by *any*
polynomial-time test, assuming the intracability of the QRP. The above
are all polynomial time, so, yes, it covers them.
> Many thanks in advance. (Please give pointers to paragraphs
> of the original BBS article, if possible, so that one could
> read them up eventually.)
I don't have the article here: it's on a CD at home.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: New William Friedman Crypto Patent (filed in 1933)
Date: Tue, 15 Aug 2000 12:13:37 GMT
As I noted, U. S. Patent 4143978 was for a machine with pinwheels, so
it couldn't have been "The SIGABA patent", if indeed one were applied
for. (It is possible that the SIGABA, along with the M-228 and M-229,
were considered so sensitive that no patent had been applied for for
those machines.)
However, it is very closely related: upon consulting primary sources,
it is now apparent to me that this patent is based upon the ECM Mark
I, the machine developed jointly by Bern Anderson and Donald J. Seiler
prior to their being informed of the new idea developed by W. F.
Friedman and Frank Rowlett.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: OTP using BBS generator?
Date: Tue, 15 Aug 2000 12:22:16 GMT
On Mon, 14 Aug 2000 23:07:53 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote,
in part:
>This whole discussion is theoretical, generally addressing the meaning
>of cryptographic proof. I'm unaware of any controversy about the idea
>that cycles theoretically could be detected easily.
No, and neither is it controversial that a PRNG that produces a short
cycle is insecure cryptographically, at least if the cycle is
sufficiently short (I'm assuming something you've said in a post
elsewhere in this thread refers to "short" in another sense - short
compared with the maximum possible output, but not short compared to
the length of messages).
Since there is a 'mathematical proof' that the output of a BBS
generator is "hard" to predict, in the same sense that breaking some
public-key ciphers is known to be "hard" (it could be easy, but only
if a better method of factoring is discovered than any we now know
of), I would, however, have to conclude that it is also a proof that a
BBS generator cannot produce only a short cycle (when used in the
manner the proof refers to: i.e., its output is not hard to predict if
the seed is zero).
Otherwise, the proof would have to be flawed, I would think.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Looking for password statistical data
Date: Tue, 15 Aug 2000 14:37:47 +0200
Seeker wrote:
>
> I'm looking for some data on the passwords that people have chosen. I know
> people often choose dictionary words, etc, but I am looking for something
> which I can draw some concrete conclusions from. Of course, the bigger the
> sample, the better.
Sorry for raising an issue that 'distracts' from your theme.
But, seeing that this thread has so far got only one follow-up,
I could possibly be allowed to do so without causing big harm.
In a large number of applications people are asked to supply
a password of only 8 characters. Is it really that very hard
to determine that through e.g. casting a die and remember
the result by heart (keeping a copy in some presumably
secure place to avoid the consequence of fading memory)?
I mean in most cases it should work well. (I am not
assuming very mighty opponents, etc.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Crypto Related Professional Attitude
Date: Tue, 15 Aug 2000 14:37:57 +0200
Mark Wooding wrote:
>
[snip]
> [1] Of course, it might have been an imposter, but if all imposters are
> that helpful and intelligent then I think we could do with more of
> them.
I have absolutely nothing against you opinion above. But I
find it interesting nonetheless that the prudence in crypto
carries over in this context, reminding us to be careful
everywhere, which is certainly proper.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Tue, 15 Aug 2000 14:38:02 +0200
Mark Wooding wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > So we know the size of these. But what useful implications do they
> > have in this context (i.e. concerning 'difficulty'), if these are not
> > otherwise made definite/clear? BTW, do we have sort of 'meter' for
> > rigorously quantifying that 'difficulty'? Thanks.
>
> No. I left my description deliberately vague. Our understanding of
> what numbers are particularly hard to factor will change as we get
> better at factoring, and it will change in an unpredictable way.
>
> Currently, our best general-ish factoring method takes time related only
> to the size of the number being factored. So we just choose `big'
> numbers. This might change.
>
> It might not.
My point is that at any given time, e.g. now, we'll have
difficulty of rigorously quantifying the 'difficulty' in
question? Should we measure it in terms of cpu-time of
factoring the given numbers by a 'particular' algorithm,
or what? (The choice of the algorithm would be an issue.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Crypto Related Professional Attitude
Date: Tue, 15 Aug 2000 14:52:48 +0200
Mark Wooding schrieb:
>
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> > Safuat Hamdy wrote:
> > > I doubt that one can seriously learn anything in sci.crypt.
>
> Oh, I learn new things all the time. Even the really bad `can't
> possibly be insecure' fake one-time-pads sometimes throw up interesting
I think that his word 'serious' also implies that part of
the stuffs in the group are not of 'serious' nature (in
the sense of some of the chats of old ladies at coffee time).
Certainly one can also learn from 'bad' things, at least in
one point, namely to avoid doing that oneself. The question
is whether it is cost-effective to study stuffs with a very
low percentage of really useful informations, i.e. whether
there are not other alternative ways of learning that can
much better help you to proceed for attaining your learning
goal.
M. K. Shen
------------------------------
Subject: Re: Impossible Differentials of TC5
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 15 Aug 2000 05:40:49 -0700
Yeah, but TC5 uses smaller and smaller feistels so it is NOT
sufficient to send the 128-bit difference (d, 0) (64-bit
quantities) into the structure and expect it to work.
The quantity 'd' has to allow for the impossible differentials
in the smaller feistels or it won't work.
Tom
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: Big Brother Is Reading Your E-Mail
From: tomstd <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy,alt.security.pgp
Date: Tue, 15 Aug 2000 05:42:15 -0700
Michael Brown <[EMAIL PROTECTED]> wrote:
>Currently, I can do a 12 bit by hand, an I'm writing up a word
documant
>to be posted soon. If you want to see an old and not-complete
version in
>XL form go to:
>http://members.fortunecity.com/mibro/rsa.xls
>My copy of Netscape doesn't want to download it directly, but
any
>downloader such as GetRight or NetVampire does it fine.
>
>There is still a bug not mentioned on the XL sheet. It's when
the second
>least significant bit is zero, and this is what I'm writing up
at the
>moment. However, you still can factorize a key of any size with
the 2nd
>LSB being one. Just add more boxes (se the sheet for details).
>
>PS: Half the stuff on the sheet is probably very jumbled. This
is why I
>didn't release it sooner.
>
>
I think your method is more alchemy then science, since I can't
read XL files I can't see your method.
BTW 12 bit composites are easy to factor even by hand.
Tom
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: OTP using BBS generator?
Date: Tue, 15 Aug 2000 12:43:33 GMT
On Tue, 15 Aug 2000 05:04:51 GMT, Bryan Olson <[EMAIL PROTECTED]>
wrote, in part:
>> Bryan Olson wrote:
>> : Many times on sci.crypt people have objected to the proof of
>> : perfect secrecy for the OTP based on the fact that the zero
>> : vector is one of the possible keys. The false logic goes
>> : something like: since the OTP is provably secure, and zero
>> : is a legal key, then encrypting with the zero key must be
>> : secure, and since it obviously isn't the proof must be
>> : wrong.
Well, I haven't "objected to the proof of perfect secrecy for the
OTP", but I have noted that people might be tempted to reject the
all-zero key, despite the fact that this, from a theoretical point of
view, is wrong.
I even went as far as to defend this practice as being not all that
bad. Perhaps this makes me a heretic, but I don't think it goes
against truth in the practical sense.
>> : The OTP theorem doesn't say that encrypting with a
>> : particular key will maintain secrecy. It says choosing a
>> : one-time key uniformly at random and exposing the resulting
>> : ciphertext does not increase the chance of the attacker
>> : determining the plaintext.
quoting somebody else:
>> This case still seems totally different from the case of
>> using BBS with short cycles.
>> Using the all-0 key in an OTP doesn't help the attacker
>> get the message, since he has no way of knowing it has been used.
This is true in a theoretical sense.
>Not so. If in fact one does use the all zero key of
>significant length, the attacker should win. He would
>almost certainly think we were not in fact using a true one
>time pad. There's nothing in the theorems that will stop
>him from reading cleartext.
I agree with that.
So how do we *reconcile* these two points of view? How can we take the
undeniable truths of mathematics, and the practical facts of
common-sense, and show that they don't really contradict each other?
Hint 1: Let's say someone went further, and decided to apply a binary
OTP to a message in 8-bit ASCII characters. However, to make it simple
to avoid an all-zero pad, the OTP was modified so that *no byte in the
pad was ever 00000000*.
Clearly, this _would_ compromise security.
>Using the OTP, the chance of any message given the
>ciphertext is the same as the chance of that message when
>not given the ciphertext. That follows from the uniform
>keyspace; if you try instead the conditional probabilities
>given specific keys, the secrecy of the system vanishes, as
>Shannon warns up front.
Now, this doesn't seem to say more than that even the OTP is not
secure if the attacker _knows_ the key, so that doesn't seem to be
germane. Whatever the problem is, it isn't that the attacker *knew*
you were going to use an OTP with 000...000 on it.
>An attacker's chance of factoring a known modulus given BBS
>output (from a random starting point) is the same as his
>chance without the generator output. Again, that follows
>from the space of possible choices.
>The two systems certainly are different, and the title of
>this thread is unfortunate, since BBS has nothing to do with
>the OTP. The issue that secrecy comes from the keyspace and
>not the key applies to all secrecy systems.
But that is what the *other* poster said, in effect. The fact that the
OTP value didn't *have* to be zero is claimed to give secrecy - even
in the case where the key happened to be zero.
As you note, though, the real problem is that the attacker will see
the message, and assume that it was sent in the clear because it looks
like plaintext.
Besides rejecting the all-zero pad, how far should one go, though?
Presumably, on the basis that the attacker does not know that an OTP
is being used, but will consider other, lesser, systems, one should
(!)
reject all pads that correspond to any XOR stream cipher that could be
solved on the basis of a single message of the same size as the pad.
(!)
Thus, for example, a pad consisting entirely of a short, repeated,
sequence of bytes should also be rejected.
But if we keep going on like this, we have made the keyspace smaller
than the message. So if the attacker knows what we're doing, he
clearly can derive *some* information about the message. Of course, we
will, even in a fairly extreme case, reject _less than half_ of the
possible keypads, and so the information about the message will amount
to no more than *a single bit*.
So, if anyone is nervous about spoiling the theoretical security of
the OTP based on rejecting patterned keypads, there is an easy cure.
Add 56 random bits to the start of the message - and encipher the rest
of it in DES with that key. Now, since there are 2^56 possible inputs
to the OTP process that contain the same message, knowing one bit of
the input to the OTP process won't help you - you have to know the
equivalent of 56 bits before you can even start learning anything
about the real plaintext. (And, of course, you would have to know 56 +
64 bits before doing so became "easy", or rather trivial, but knowing
fewer bits than that will, at least if they're in the right places,
allow some cryptanalysis.)
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Jonathan Thornburg)
Subject: Re: What is up with Intel?
Date: 15 Aug 2000 14:52:02 +0200
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>I recall hearing as long ago as 1983 about a small company
>(whose name I have forgotten but would recognize if I heard)
>that held the patent on use of XOR to undraw/redraw, as in
>cursor bitmap images. Since this is obvious and essential
>technology, it raised quite a stink when they tried to
>collect royalties.
Another such case... a company in Russia recently received a Russian
patent on the combination of concave and convex surfaces, and surface
thicknesses, in a beer bottle. They're currently trying to get 1.5%
royalties from all the beer manufacturers in Russia. Sigh...
[[no, this is not an urban legend... source is an article by a
local resident in the most recent issue of the Manchester Guardian
Weekly newspaper]]
--
-- Jonathan Thornburg <[EMAIL PROTECTED]>
http://www.thp.univie.ac.at/~jthorn/home.html
Universitaet Wien (Vienna, Austria) / Institut fuer Theoretische Physik
Seen on usenet (dueling .signature quotes):
#1: "If we're not supposed to eat animals, why are they made of meat?"
#2: "If we're not supposed to eat people, why are they made of meat?"
------------------------------
From: Anders Thulin <[EMAIL PROTECTED]>
Subject: Re: Looking for password statistical data
Date: Tue, 15 Aug 2000 12:59:38 GMT
Seeker wrote:
> If there is a large list of passwords that people have actually used
> somewhere not associated with any names, companies or systems that would
> allow me to do my own analysis, that's fine. Thanks.
One of the most common choices of passwords (IMHE) are passwords related
to either the account name or the personal name of the account owner. But in
order to determine if the password Ajax is the name of the account, the name of
the account owner, the major piece of software running on that
computer, the company from which the password file comes or the dog of the
account owner (or even her husband), you really have to have all those associations
still remain somehow. If not, it just becomes a general 'name' password.
Daniel Klein's paper (already mentioned) is still valid, I believe.
See http://www.klein.com/security.
If there are any later studies of passwords -- I don't know of any --, you
should be able to find references to them at the Coast archive now at
www.cerias.purdue.edu.
--
Anders Thulin [EMAIL PROTECTED] 040-10 50 63
Telia Prosoft AB, Hj�lmaregatan 3B, 212 19 Malm�, Sweden
------------------------------
** 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
******************************
