Cryptography-Digest Digest #308, Volume #11 Sun, 12 Mar 00 06:13:02 EST
Contents:
Re: sci.crypt Cipher Contest Web Site ([EMAIL PROTECTED])
Re: How does % operator deal with negative numbers? ("Douglas A. Gwyn")
Re: Big Float project ("Douglas A. Gwyn")
Just *Germain* primes ([EMAIL PROTECTED])
Re: why xor?(look out,newbie question! :) ("Douglas A. Gwyn")
Re: why xor?(look out,newbie question! :) ("Douglas A. Gwyn")
Re: NSA Polygraph Screening Exposed ("Douglas A. Gwyn")
Re: NIST, AES at RSA conference ("Douglas A. Gwyn")
Re: Cheating in co-operative open-source games, how can we protect from it? (NFN NMI
L.)
Re: Question about sort of signing (NFN NMI L.)
Re: Just *Germain* primes ("Douglas A. Gwyn")
Re: NIST, AES at RSA conference (Mok-Kong Shen)
Re: why xor?(look out,newbie question! :) (Mok-Kong Shen)
Re: Concerning UK publishes "impossible" decryption law (Lincoln Yeoh)
Re: Concerning UK publishes "impossible" decryption law ("�R���")
Re: Concerning UK publishes "impossible" decryption law ("Stormshadow")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: sci.crypt Cipher Contest Web Site
Date: Sun, 12 Mar 2000 05:07:39 GMT
In article <8aavrt$2ibo$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> My first choice for this contest would be scott16u with the changes
> that someone offered to make it more compatible. And yes if AES block
> ciphers used "wrapped PCBC" and 3 or 4 passes used they would have
> most of the properties that I feel are needed except for the tiny key
size
> they use. But I have never seen anyone offer any of them in that kind
of
> operational mode.
> >
...
> David A. Scott
>
Mr. Scott,
I will start the cryptography discussion with your scot16u algorithm.
I took a look at your web page to get the specification. I am still a
bit unclear on the details but I have a few questions.
Here is a quick description. Have I made any mistakes?
Cn = S[((Cn-1^Pn)+Pn+1)mod 65535] seems to be the F function for the
cipher.
The strength of the cipher resides in the secrecy of the SBOX. The
SBOX is a bijective 2^16 linear array. The SBOX is generated via a non
linear process involving the secret key and a starting SBOX.
The cipher text is rotated 10 bits after each pass. The previous
round's cipher text is used as the plain text in the next round. At
the end and begining of the plain text the text is wrapped so that Cn-1
for the first round is actually the last word of the orginal plaintext.
So far so good?
Here is my question. Is there anything preventing a collision in the
SBOX of the form?
k = S[k]
If not suppose we have a file full of k's. Further suppose k is a ten
bit rotation of itself. All '1' or all '0' are easy examples.
Now if the entire file is one 'k'
Cn = S[((Cn-1^Pn)+Pn+1)mod 65535]
Cn-1 = k because of the wrap
Pn = k the first word in the file
Pn+1 = k because of the wrap
Cn = S[((k^k)+ k) mod 65535] = k
No matter how many rounds are applied, the cipher text is the same as
the plain text, a most suprising result. Have I made a mistake?
Ten bit rotations are common, I believe there are 2^6 of them below
65536. If the values of the sbox are random, the chance of a value
equaling itself is 1 in 2^16. So one key in every 2^16/2^6 = 2^10
yields a weak value. Is that right?
--Matthew
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.javascript
Subject: Re: How does % operator deal with negative numbers?
Date: Sun, 12 Mar 2000 06:05:30 GMT
Dr John Stockton wrote:
> (1) "Which is the function that % or MOD should give"? Ideally, I'd say
> the first; but the second is too traditional to change.
The problem is, in C89 at least, which of the behaviors you get is not
specified. In C99, integer division (/ operator) truncates toward 0.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Big Float project
Date: Sun, 12 Mar 2000 06:36:01 GMT
Tom St Denis wrote:
> > z^2 + 3z - 5 = 0 is an equation which we can solve for z.
> So I can expand that to (a + ib)(a + ib) + 3(a + ib) -5 = 0, a^2 + 2aib +
> (ib)^2 + 3a + 3ib - 5 = 0, a^2 + 3a + 2aib + ib^2 - 5 = 0.
(ib)^2 is -b^2, not ib^2, and you lost a term 3ib.
The substitution you made doesn't really help solve the equation;
separating the real and imaginary parts, you now have to solve a
system of 2 equations:
a^2 + 3a - b^2 - 5 = 0 (real part)
2ab + 3b = 0 (imaginary part without the i)
Of course, the second equation implies b = 0 or a = -3/2:
If b = 0, the first equation becomes a^2 + 3a - 5 = 0, which is
the same equation we started with (it has two real solutions).
If b != 0, a = -3/2, the first equation becomes b^2 + 29/4 = 0,
which has no real solution.
So all that work just reduced the problem to finding the two
real solutions of the original equation!
For a more instructive example, start with z^2 + 3z + 5 = 0:
If b = 0, the first equation becomes a^2 + 3a + 5 = 0, which is
the same equation we started with (it has *no* real solution,
and since a is real, this branch is a dead end).
If b != 0, a = -3/2, the first equation becomes b^2 - 11/4 = 0,
which has two real solutions b = +- sqrt(11)/2.
So the two (complex) solutions are z = -3/2 +- i sqrt(11)/2.
If you just use the quadratic formula directly on the original
equation, using sqrt(-1) = i, you get the same result. Most
people find this easier.
> What is z' is that (a - ib) ?
Yes. Indeed, for every complex solution to an equation written
purely in terms of real parameters, the conjugate also solves
the same equation. One way of thinking about this is that in
extending the real number system to complex numbers, the key
is to define an imaginary unit i such that i^2 = -1, but then
(-i)^2 = -1 also, so you could have used the negative of the
imaginary unit and gotten the same properties. Thus "conjugating"
(replacing i by -i) gives you an equivalent extension of the reals.
> > satisfy the equation z^n = 1 are called "nth roots of unity".
> I assume n is a real? How do you find n?
n is a given integer. n being given, you don't find it; what
is sought are the (complex) values of z that have the property
that z^n = 1. For example:
n = 1: z = 1.
n = 2: z = 1 or -1.
n = 3: z = 1 or -1/2 + i sqrt(3)/2 or -1/2 - i sqrt(3)/2.
n = 4: z = 1 or i or -1 or -i.
------------------------------
From: [EMAIL PROTECTED]
Subject: Just *Germain* primes
Date: 11 Mar 2000 22:21:33 -0800
In article <[EMAIL PROTECTED]>,
John Savard <[EMAIL PROTECTED]> wrote:
>enough) a little mistake in the documentation; the numbers turned up
>in the Sophie Germain mode are the ones usable as actual moduli.
May I say something almost entirely off-topic and annoying? Thank you.
I think that these numbers, whether you choose to define them as primes
that are one greater than twice other primes, or as primes that you can
double and add one to, to get other primes, ought to be called "Germain
primes", not "Sophie Germain primes". I realise that my holding that
opinion isn't going to change the existing literature, nor very many
people's minds, but I still think it's worth mentioning.
Why do I think this? Well, established tradition in the mathematical
community is to name mathematical objects with the surname(s) of the
person(s) we wish to honour. Thus "Abelian group", "Mandelbrot set",
"Huffman code", and "Diffie-Hellman key exchange". Not "Niels Abelian
group", "Benoit Mandelbrot set", "David Huffman code", nor "Whitfield
Diffie-Martin Hellman key exchange". I can't think of anything in math
that is named with both of someone's names... except "Sophie Germain prime".
Adding a person's given name might be appropriate if we wanted to
distinguish them from someone else with the same surname, but I can't
think of an actual example of that in a commonly used mathematical term.
We say "Blum-Blum-Shub pseudorandom number generator" without trying to
indicate which Blum is which or distinguish either of them from the other
mathematicians named Blum who doubtless exist. And I don't know of any
other famous mathematician named Germain whom Sophie Germain might be
confused with. So that excuse seems to be a non-starter.
What, then, is different about Sophie Germain that we'd single her out in
this unusual way? I'm afraid the answer is obvious, and it doesn't
reflect well on the mathematical community. It would be much more
appropriate to honour her in exactly the same way we'd honour anyone else
of similar accomplishment.
--
Matthew Skala "Ha!" said God, "I've got Jon Postel!"
[EMAIL PROTECTED] "Yes," said the Devil, "but *I've* got
http://www.islandnet.com/~mskala/ all the sysadmins!"
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: why xor?(look out,newbie question! :)
Date: Sun, 12 Mar 2000 06:56:41 GMT
Mok-Kong Shen wrote:
> Please note that 'uncorrelatedness' is not identical to 'independence'.
There is a necessary connection, if by "independence" you mean
anything at all like the probability-theoretic meaning of that term.
I interpret your question as being, do *corresponding* bits of two
stateless bit sources A,B correlate as would be expected if P(1) for
source A were independent of P(1) for source B. That is the same as
asking about their correlation. I think the real problem is that
you haven't formulated a sufficiently precise question. If you mean
something else, you should explain your terminology.
> So please now tell me how am I going to apply the
> Peason chi-square test to test the independence of two bit sources.
The usual way -- you set up a suitable null hypothesis, which for
chi-square testing would be that the streams come from the same
population, and if your test results do not support that hypothesis,
that is evidence in favor of the contrary: the streams do not come
from the same population. That is *some* degree of "independence".
Again, the information statistic is better than chi-square for
such tests. Because it is asymptotically chi-square, the same
inverse probability tables can be used to look up its significance.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: why xor?(look out,newbie question! :)
Date: Sun, 12 Mar 2000 07:01:04 GMT
"r.e.s." wrote:
> Suppose your bit streams are a_i and b_i (i=1..n). You're asking
> about independence "between streams" (a_i)(i=1..n) and (b_i)(i=1..n).
> But to address that, it happens that the tests mentioned require an
> assumption that (a_i, b_i)(i=1..n) are mutually independent.
Actually, they don't require that assumption, but they of course
have less discriminating power when it's not true. If they find
a significant correlation, it is still significant; if they don't
find a significant correlation, it may still be the case that some
other form of correlation exists but went undetected.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: NSA Polygraph Screening Exposed
Date: Sun, 12 Mar 2000 07:18:31 GMT
Frog wrote:
> If you are assigned to NSA or pending assignment, you need to know
> about the deception behind the DoD polygraph test.
Why? All the prospective employee can do is to ask that his
objection be attached to the record. And if you annoy the polygraph
examiner, he might bias his readings against you. I think the only
thing that could help would be a class-action suit, brought by people
who have innocently "failed" the polygraph exam. (The actual
evaluation is not normally "pass/fail", it's a list of suspect
responses to specified questions.)
> The test has no scientific validity whatsoever, and it depends on the
> polygrapher tricking the subject ... into making damaging admissions.
The galvanic responses do indicate nervous perspiration, excited
heart rate, etc. The examiner can discover negative information
through "tricking" the subject into getting nervous about that
information. There is a real danger that the nervousness might be
due to some non-security cause, such as not wanting to make
embarrassing admissions about one's personal life. The questions
are supposed to be discussed in advance with the subject to prevent
this.
I will agree that some individuals can respond truthfully and be
"detected" as lying, and vice versa. One can be trained in how
to beat a polygraph.
I also agree that polygraph examination was adopted too readily
and that too much trust has been placed in its reliability.
Most claims I've seen about its track record have not been based
on objective testing to the standards generally accepted in the
medical research community, for example.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Date: Sun, 12 Mar 2000 08:30:38 GMT
"David A. Wagner" wrote:
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> > The assumption was that FH is readily crackable, but FG and G'H
> > are not. For example, suppose F, G, G', and H each uses 32 bits
> > of key and that FH can be cracked using radically less work than
> > a brute-force key search, but FG and G'H cannot. 2^-32 of the
> > time, the composite system cracks immediately; that is much worse
> > than either separate system FG or G'H.
> How on earth can that be?
Because breaking FG or G'H requires ~2^63 "macro" operations in
every case, whereas breaking FGG'H requires at least that many
macro operations in almost every case but nearly no operations
2^-32 of the time. If the safety criterion is that there is
*no feasible attack* for more than 1 - 2^-32 of the traffic,
then the latter system fails.
> ... <= 2^32 Break(FH) (because FH is at least as strong as F)
I think you're assuming the "theorem" you're trying to prove. FH
is, by assumption, very easy to crack. But that's not the real
issue. (You may have identified a need for the cryptosystem
designer to recursively check that FH is not weaker than either
of *its* components.)
> You note that 2^-32 of the time, FGG'H breaks with workfactor Break(FH).
> If we assume this is the best attack on FGG'H, then
> Break(FGG'H) = Break(FH) / 2^-32
I disagree there. That analysis is for breaking FGG'H in the
*general* case, which is not my concern. My concern is the
likelihood of *any* break, not of *every* break. To me, the
loose term "security of the cryptosystem" has to do with the
*worst case* (for the legitimate users), not the *typical* case.
Maybe we should call it "minimum guaranteed level of security",
assuming we have advanced far enough analytically to make such
guarantees.
> There's an alternate way to view it. We can start from the
> assumption that the best attack on FGG'H is to hope that GG' =
> identity (happens with prob. 2^-32) and to optimistically apply
> the attack on FH to the data from FGG'H.
Absolutely. That is how one would actually exploit the weakness.
An intelligence agency might analyze traffic if it expects that
one message in 2^32 will be deciphered for some small amount of
work (after that much work is attempted against a message, it
would be abandoned), but it might not try to decipher any
message at all if 2^63 macro operations are required per success.
2^32 is not such a large number when you consider really
high-speed communications.
------------------------------
From: [EMAIL PROTECTED] (NFN NMI L.)
Subject: Re: Cheating in co-operative open-source games, how can we protect from it?
Date: 12 Mar 2000 08:56:12 GMT
<<Remember the anti-SDMI creed:
If I can see it, I can record it.
If I can hear it, I can record it.
If my computer can execute it, I can comprehend it.
I can teach these abilities to others.>>
Who first said this? I maintain a small quotations page (http://quote.cjb.net/)
and I'd like to add it if I could attribute it to its original author.
Thanks!
S. T. L.
------------------------------
From: [EMAIL PROTECTED] (NFN NMI L.)
Subject: Re: Question about sort of signing
Date: 12 Mar 2000 09:02:01 GMT
<< as the channel is a shared resource>>
Pro'lly USENET, eh? Whatever. Sometimes I get the feeling I'd like to know
what's behind all these mysterious posts on sci.crypt.
S.T.L.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Just *Germain* primes
Date: Sun, 12 Mar 2000 09:04:10 GMT
[EMAIL PROTECTED] wrote:
> ought to be called "Germain primes", not "Sophie Germain primes".
Absolutely; I was startled by the discovery that most of
the usages found in a Web search included "Sophie".
The real problem with "discrimination" has always been the
judging of individuals in terms of stereotypes instead of
on their own merits. (I put that in quotes because in the
conceptual context it is actually a *lack* of discrimination.
In the social context it means treating certain people
differently from others, which isn't inherently bad, only if
done on some irrational basis such as stereotyping.)
Political attempts to redress past wrongs by "reverse
discrimination" are wrong for precisely the same reason; it's
still judging people via inessential, accidental properties.
I have no idea if Blum, Blum, and Shub are male, female,
black, white, yellow, red, green, hairy, bald, skinny, fat,
etc. What does it matter insofar as mathematics is concerned?
Let's honor Sophie Germain by treating her as an equal member
of the mathematical community: "Germain primes". (Def:
primes p for which 2p+1 is also prime.)
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Date: Sun, 12 Mar 2000 11:34:13 +0100
Terry Ritter wrote:
>
> We simply must face the inability of mathematical cryptography to
> prove any practical cipher secure. Since no cipher is proven secure,
> we also must face the possibility of weakness in any cipher, including
> all of those constructed or reviewed by academics and government
> agencies.
>
> We can theorize about how one possibly weak cipher is just the same as
> any other possibly weak cipher with respect to mathematical strength
> (in which case we might as well use newbie ciphers), or we can propose
> realistic possibilities to deal with possible weaknesses using the
> resources we already have.
>
> I claim we can address the problem of accidentally using one or even
> two weak ciphers by using three ciphers in a multicipher stack.
>
> I claim we can address the problem of a possible break of any single
> cipher we use by changing to another cipher. That of course requires
> multiple ciphers, as well as the ability to change ciphers.
>
> And we can address the problem of a possible break of all three
> ciphers in a stack by changing to another stack.
Tiny remark: One could probably introduce some dynamics into the
stack through permuting the elements and/or choosing m of n.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: why xor?(look out,newbie question! :)
Date: Sun, 12 Mar 2000 11:34:08 +0100
Douglas A. Gwyn wrote:
>
> Mok-Kong Shen wrote:
> > Please note that 'uncorrelatedness' is not identical to 'independence'.
>
> There is a necessary connection, if by "independence" you mean
> anything at all like the probability-theoretic meaning of that term.
> I interpret your question as being, do *corresponding* bits of two
> stateless bit sources A,B correlate as would be expected if P(1) for
> source A were independent of P(1) for source B. That is the same as
> asking about their correlation. I think the real problem is that
> you haven't formulated a sufficiently precise question. If you mean
> something else, you should explain your terminology.
Independence of random varaibles is defined in any textbook of
statistics. You think I need to cite the definition?
>
> > So please now tell me how am I going to apply the
> > Peason chi-square test to test the independence of two bit sources.
>
> The usual way -- you set up a suitable null hypothesis, which for
> chi-square testing would be that the streams come from the same
> population, and if your test results do not support that hypothesis,
> that is evidence in favor of the contrary: the streams do not come
> from the same population. That is *some* degree of "independence".
>
> Again, the information statistic is better than chi-square for
> such tests. Because it is asymptotically chi-square, the same
> inverse probability tables can be used to look up its significance.
I repeat: My problem is testing independence, with the term EXACTLY
having the meaning defined in textbooks of statistics. The
null hypothesis has consequently to be formulated with that
definition in mind. If you could mathematically show that your
'from/not-from the same population' is equivalent to
'dependence/independence' and then derive the test statistics
based on your notion, I don't mind.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Lincoln Yeoh)
Crossposted-To:
alt.security.pgp,comp.security.pgp.discuss,alt.security.scramdisk,alt.privacy
Subject: Re: Concerning UK publishes "impossible" decryption law
Date: Sun, 12 Mar 2000 10:29:20 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 11 Mar 2000 22:02:15 GMT, [EMAIL PROTECTED] (JimD)
wrote:
>I like that. After you've finished with the computer for the day, have
>a switch which connects the case to the live side of the supply and
>have lots of earthed (grounded) metal in the vicinity. Arrange it so
>that the computer melts and takes the Pig with it!
I was thinking more of thermite. Mains ain't good enough and semtex is way
too much - plus the police will have a good excuse to detain you.
What would be a safe way to do it? Maybe if it's about to go off it beeps a
few times, then you better press a button to disarm.
You can most certainly prevent people from opening up the casing.
Can people actually disarm most bombs? Or they just blow em up in a
controlled manner? Should be trivial to prevent people from opening stuff
up and disarming it.
>Jim Dunnett.
>dynastic at cwcom.net
>Exiled in Somerset
>Right at the heart of England's BSE Industry.
Hey what happened to your old address? You now in cow zone? Great
atmosphere eh? ;).
Link.
****************************
Reply to: @Spam to
lyeoh at @[EMAIL PROTECTED]
pop.jaring.my @
*******************************
------------------------------
From: "�R���" <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security.pgp.discuss,alt.security.scramdisk,alt.privacy
Subject: Re: Concerning UK publishes "impossible" decryption law
Date: Sun, 12 Mar 2000 00:34:25 +1100
i have been trying to work out a way of using the windows login to booby
trap the hd, say if they ask you what your logon is, and you tell em its
your name and ph number, when its not, and they use it, poof, a batch file
wipes all sensitive data and does a pgp free space wipe as it boots up, i
can figure out how to write the batch file, but not where to put it, perhaps
in the new user run once registry line? any ideas?
--
"Oh GOD, Please save me from your followers"
more of my ramblings can be found at http://oakgrove.mainpage.net
"Man is a part of nature, not apart from nature"
anti spam, replace "at" with "@"
ICQ:16544782
"Lincoln Yeoh" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Thu, 09 Mar 2000 01:32:33 GMT, [EMAIL PROTECTED] (Ian L.
Romkey)
> wrote:
>
> >Logically impossible? Maybe not. I don't live in the UK myself, but for
> >British subjects, it might turn out that my password grid strategy
> ><http://www.5x5poker.com/grid/> could provide an effective escape from
this
> >rather invasive and unfair law. Remember that an important feature of the
> >strategy is that in the event the password grid in use is destroyed,
other
> >unused grids should be retained in order to demonstrate how the grids
work.
> >Perhaps the ability to provide this demonstration could remove the
> >"reasonable grounds" mentioned above in Clause 46.
> >
> >On the other hand, maybe it's a bad idea. What do you think?
>
> I think if you destroy the grid when they're rapping on your door, you're
> still in big trouble. If you did it long before then maybe. Maybe you
> should have had your key revoked too.
>
> How about you booby trap your computer and tell them NOT to touch your
> computer. They touch it and poof everything melts to slag, then it's not
> your problem, as you already told them NOT to touch it.
>
> Trouble is doing it in a safe way so that it doesn't trigger during normal
> operation - e.g. kid brother whacks/moves the computer. But most people do
> not and should not use such methods. Would be silly to do so.
>
> Cheerio,
> Link.
> ****************************
> Reply to: @Spam to
> lyeoh at @[EMAIL PROTECTED]
> pop.jaring.my @
> *******************************
------------------------------
From: "Stormshadow" <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security.pgp.discuss,alt.security.scramdisk,alt.privacy
Subject: Re: Concerning UK publishes "impossible" decryption law
Date: Sun, 12 Mar 2000 12:03:52 +0200
"JimD" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I like that. After you've finished with the computer for the day, have
> a switch which connects the case to the live side of the supply and
> have lots of earthed (grounded) metal in the vicinity. Arrange it so
> that the computer melts and takes the Pig with it!
But if you'd like to use your computer later, the switch should be safe to
touch, even for the authorities. And if you're a _really_ bad person, the
authorities will cut your power before busting in.
And even if this booby-trap works, you would be charged with assaulting a
police officer or even a murder if your booby-trap is really effective. ):-)
--
Stormshadow <[EMAIL PROTECTED]>
http://www.saunalahti.fi/hirvox/
------------------------------
** 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
******************************
