Cryptography-Digest Digest #889, Volume #11 Mon, 29 May 00 20:13:01 EDT
Contents:
Re: No-Key Encryption (Bryan Olson)
Are Anonymous Broadcast Protocols Any Good? (zapzing)
Re: Math problem (P=NP) prize and breaking encryption (David A Molnar)
Re: encryption without zeros (Mark Wooding)
MDS theory? (tomstd)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May ("Axel")
Re: Math problem (P=NP) prize and breaking encryption (root)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May ("Axel")
Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
("Axel")
Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
("Axel")
Re: No-Key Encryption (Bryan Olson)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (David Boothroyd)
Re: Is OTP unbreakable?/Station-Station (Bryan Olson)
Re: encryption without zeros (lcs Mixmaster Remailer)
----------------------------------------------------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Date: Mon, 29 May 2000 22:18:18 GMT
Michael Pellaton wrote:
> Now, what's the proper English name for what I described above?
It's a (weak) form of Shamir's "Three-Pass Protocol". A
reasonable function to replace XOR is exponentiation mod
p, where p is a large prime (and (p-1)/2 should also be
prime). It doesn't hold up if attackers can generate or
modify the messages.
> Where is it used?
> Are there any well-known implementations?
I don't know that it has ever been used. It doesn't have
any great advantage over Diffie-Hellman key exchange, though
it is kind of cool.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Are Anonymous Broadcast Protocols Any Good?
Date: Mon, 29 May 2000 22:20:13 GMT
I was reading in "Applied Cryptography" about anonymous
broadcast protocols. The main idea goes something like this
Everyone is sitting at a table and everyone flips a coin
in such a way that he and the person sitting to his right
can see it, but noone else. Then everyone considers the
two coins he has seen flipped, and announces "same" or
"different". Except, if a person wishes to "broadcast"
a "1" then he lies in his anouncement of "same" or
"different". If only one person is "talking" on the
channel the it is easy to see if the broadcast message is
a "1" or a "0".
Anyone can disrupt the channel, unfortunately, by
broadcasting random bits. Comes with the territory.
there can also be unintentional interference if
two people try to talk at the same time. this can easily
be overcome.
However, it occured to me that another problem with this
protocol is that an anonymous broadcaster could be
'revealed" by a conspiracy consisting of the two people
sitting on both sides of him. It also occured to me that
the protocol could be modified if everyone flipped a
coin with everyone else. Then it would take a conspiracy
of n-1 to reveal a broadcaster. But then what would be the
point, if everyone could talk to everyone else anyway?
What I'm asking is, I guess, are there any anonymous
broadcast protocols that do not have this conspiracy
of 2 problem?
Also, would there be any advantage to the anonymous
broadcast protocol I mentioned above, where everyone
flips a coin with everyone else?
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Math problem (P=NP) prize and breaking encryption
Date: 29 May 2000 22:19:07 GMT
Axel Lindholm <[EMAIL PROTECTED]> wrote:
> Thank you for enlightening me! I searched for the best factorisation alg but
> without very good results, if you had a reference to a page that had some
> information on that algorithm I'd love it!
Well, there is a web site called "Factor World" which another poster
mentioned. Unfortunately I can't find the URL just now.
The fastest algorithm I know of for random RSA moduli is called the
"General Number Field Sieve." There is a short blurb on it here,
http://www.research.att.com/~bal/papers/crypto/field/node8.html
and web/library searching should turn up more. Koblitz's _Course in
Number Theory and Cryptography_ does not cover the Number Field Sieve,
but it does provide some background and earlier algorithms in a readable
way.
> Ah, while I'm still typing I might as well ask if someone ever tried dealing
> with SAT and came up with some results or perhaps know a good webpage
> dealing with SAT? My numbertheory mentor gave me a small compendium about it
> once but, sadly enough, I seem to have lost it.
Afraid I don't know what the best algorithm for SAT is now. The classic
reference on this sort of thing is Garey & Johnson's _Computers and
Intractability_, but I am not sure whether an updated version exists or
where it might be.
Thanks,
-David
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: encryption without zeros
Date: 29 May 2000 22:30:08 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
> zapzing <[EMAIL PROTECTED]> wrote:
> : There are only 256^8 possible 8 bit blocks. Imagine a directed
> : graph of all possible blocks, in which block A is connected to block
> : B iff block A encrypts into bock B. Mow this graph must consist of a
> : finite number of loops. No dendrites allowed. A loop either
> : contains a block without zeros or it doesn't. So you can see that
> : any block without zeros will eventually lead to another block
> : without zeros, through the process that "Mixmaster" described.
>
> No. I don't see that at all. In fact, it's wrong ;-|
I don't think it is.
\begin{theorem}
Let $S$ be a finite set of items, and let $f : S \to S$ be a permutation
on $S$. Let $T \subset S$ be some subset of $S$. Given an element $s
\in T$, there exists a positive integer n such that $f^n(s) \in T$.
\end{theorem}
\proof
It suffices to show that elements of $S$ form cycles under application
of $f$: if this is the case, then for any $s \in S$, there exists an
integer $n$ such that $f^n(s) = s$, thus proving the theorem trivially.
Let us assume that there is an element $s \in S$ which does not form a
cycle. A simple counting argument shows that the sequence $s, f(s),
f^2(s), \ldots$ must eventually repeat: therefore there exists a least
integer $i \ge 0$ such that, for an integer $j > i$, $f^i(s) = f^j(s)$.
I claim that $i = 0$: for if not, since $f$ is a permutation, apply
$f^{-1}$ to both $f^i(s)$ and $f^j(s)$, giving $f^{i-1}(s)$ and
$f^{j-1}$. These cannot be equal, since that would contradict the
hypothesis that $i$ is the least integer with this property; but they
must be equal, since $f$ is bijective. Thus, we must have $i = 0$.
\qed
Now, let S be the set of n-bit blocks, and let f be application of a
n-bit block cipher with a given key.
-- [mdw]
------------------------------
Subject: MDS theory?
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 29 May 2000 15:44:07 -0700
I decided to play around with the x^-1 mod p sboxes (the really
spiffy ones that don't follow sac) with the affine transform
from rijndael applied to them (I use four diff moduli).
Then I stole the MDS 4x4 from Twofish.
Problem is, I don't know how MDS's work. I know what they are
suppose todo, but not how.
Any help?
I think David was write in suggesting the usage of a MDS, it
really does help spread single bit changes, and probably a good
method to avoid differential cryptanalysis.
Another idea for 64bit processors is to choose a 8x8 MDS, then 8
diff deg 8 primitive polynomials. You can make a 64x64 sbox
from it, and use that as the F function for 128 bit block
ciphers...
Anyways, I want to use a MDS in TC2 once I better understand how
it works.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: "Axel" <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: 29 May 2000 22:48:23 GMT
Reply-To: [EMAIL PROTECTED]
In uk.legal Fergus O'Rourke <[EMAIL PROTECTED]> wrote:
> The best way to get a tyrannical government is not to vote
Not when there are limitations on standing for election and how
candidates are allowed to describe themselves.
------------------------------
From: root <[EMAIL PROTECTED]>
Subject: Re: Math problem (P=NP) prize and breaking encryption
Date: 29 May 2000 22:08:38 GMT
Boris Kolar <[EMAIL PROTECTED]> wrote:
BK# Scott Fluhrer wrote:
>> Boris Kolar <[EMAIL PROTECTED]> wrote in message
>> news:[EMAIL PROTECTED]...
>> >
>> >
>> > David Blackman wrote:
>> >
>> > > Scott Contini wrote:
>> > > >
>> > >
>> > > > Here's my 2 cents:
>> > > >
>> > > > Factoring is certainly not NP-complete (though a proof of this
>> > > > does not exist). We can factor in sub-exponential time, but the
>> > > > fastest algorithms for solving general NP-complete problems take
>> > > > exponential time.
>> > > >
>> > > > Scott
>> > >
>> > > I think there is a proof that if factoring is NP-complete, then either
>> > > P=NP, or the extended Riemann hypothesis fails. I vaguely remember this
>> > > is referenced in Garey and Johnson (but i've lost my copy). A lot of
>> > > people would consider this to prove that factoring is not NP-complete,
>> > > although technically it is not quite such a proof.
>> > >
>> > > It hinges on factoring being (almost certainly) in co-NP.
>> >
>> > Factoring is in fact in the intersection of NP and co-NP.
>> To make this correct statement more explicit, both these decision problems
>> have polynomial verifiable proofs:
>>
>> Given two integers n and a, does there (not) exist integers b>1, c such
>> that b*c=n and b<a
>>
>> In the positive case, a proof can consist of (b, c)
>>
>> In the negative case, a proof can consist of the factorization of n, along
>> with primality proofs of all the factors.
>>
>> > All problems that are relevant to public-key cryptography are there.
>> Question: is that true for all known public-key cryptosystems, or is that
>> known to be inherent to public-key cryptography?
BK# My statement was perhaps too strong. All popular problems for public-key
BK# cryptography (such as factoring, discrete logarithm) are in NP and co-NP. There
BK# may be a class of probabilistic public-key cryptography problems (such as
BK# lattice reduction,...) that may be in NP and not in co-NP. Of course, the
BK# following problems are still open:
BK# - NP =? co-NP
BK# - NP _and_ co-NP =? P
>>
>>
>> > The problem:
>> > NP and co-NP =? P
>> > is even more important, than P =? NP. It's widely believed, that the
>> answer
>> > is NO (the NO answer would also imply P /= NP).
>> >
>> > Finding a problem, that is (NP and co-NP)-complete, would also be very
>> > important for cryptography.
>>
>> Actually, I didn't think we knew of a problem that was known to be both NP
>> and co-NP, but not P, even if you made the initial assumption that NP!=coNP
>>
>> --
>> poncho
I want to thank all the people that responded to this query. I learned
a lot.
And now I would like to make a further request of you (and a small
confession).
First the confession. About 4 years ago I developed an algorithm that
seems to solve the Hamilton Cycle problem. I've only tested it on random
graphs up to 100 nodes. My exhaustive search algorithm became ineffective
at approximately 30 to 50 nodes, so I haven't been able to check the larger
graphs. It is not perfect. If there is no cycle, it is fast and right
every time. If there is a unique cycle, it is fast and finds it immediately.
The problem is if there are sub cycles or multiple cycles. As the number
of cycles grows, the solution time grows also (I suspect it grows
combinatorically). A 100 node graph took approximately 5 minutes to solve
on an Intel 486DX2 66(or maybe it was an AMD 486DX4 133). The exhaustive
search would run for days, and would still be running when a killed it.
Now the request. I realize after seeing all of your comments above that
it must seem unlikely that my claim is true. How would you go about
the process of verifying and publicizing such an algorithm if you were
me? Do I just post my (beginners C++) code on the internet or an ftp
site? Do I write an article (horrors)? I have to confess that once the
problem was solved, my interest declined quickly. I got a tepid response
on inquiries as to whether it was important (I didn't ask here).
Rehashing and improving it or documenting it seemed tedious. I moved on
to other things. The article in the paper spurred me to investigate
again, possibly pursue publication.
Thank you for any guidance you can give me.
stan
PS Maybe you will also think this is not significant. In that case I
guess you can ignore the above questions.
------------------------------
From: "Axel" <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: 29 May 2000 22:52:15 GMT
Reply-To: [EMAIL PROTECTED]
In uk.legal Peter G. Strangman <[EMAIL PROTECTED]> wrote:
>> It was not huge. Since 1983 Labour manifestos have not been huge. However
>> it is not the job of the manifesto to include the complete range of
>> policies the party intends to introduce.
> Yes it is. Anything less is dishonest. The only thing
> a voter has to go on is the manifesto. It is the party's
> declaration of what it intends to do.
I would disagree. Theoretically people should be voting for an
individual not a party.
> Failing to state
> in the manifesto something as important as this shows,
> quite clearly, that the party had grave doubts about
> its prospects of being elected were it known that it
> intended introducing such draconian legislation.
I think most of the population would not have cared.
> Doing something which is not in the manifesto is just
> as deceitful as failing to fulfil promises which are
> in it.
In that case it would be impossible to run a government since daily
changes in the world could not be responded to.
Not that I agree in the slightest with this bill I hasten to add.
------------------------------
From: "Axel" <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk
Subject: Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
Date: 29 May 2000 22:56:07 GMT
Reply-To: [EMAIL PROTECTED]
In uk.legal JimD <[EMAIL PROTECTED]> wrote:
> The odds are stacked against the right-wing pillocks of the
> Security Service breaking even a Boy-Scout cipher.
> The balance of likelihood is that the only way it can be
> compromised is by getting the key by some means other than
> cryptanalysis.
Which is exactly what they would do, perhaps by seizing the originating
computer and examining it for temporary documents or simply remote
monitoring of the screen either by tempest, or even something as simple
as a bug... don't forget the videoing of the accused in the Lawrence
affair.
------------------------------
From: "Axel" <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk
Subject: Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
Date: 29 May 2000 22:59:07 GMT
Reply-To: [EMAIL PROTECTED]
In uk.legal Garry Anderson <[EMAIL PROTECTED]> wrote:
> As all your work and social communication comes to be done on the Internet,
> the greater your lack of privacy.
> You will have a permanent phone tap, for them to do with as they will.
> The dangerous criminals and terrorists will get round this - so who do you
> think they are going to be looking at?
Of course they will - simply use a mobile to connect to a
foreign ISP and use secure encryption.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Date: Mon, 29 May 2000 23:03:12 GMT
Trevor L. Jackson wrote:
>
> Michael Pellaton wrote:
>
> > It seems to me that I used the wrong name of a method of encryption.
> > Maybe it's an error that occurred during translation from and to
> > German (I have seen the word "no-key encryption" in at least two
> > German books).
> >
> > I'd like to explain what I mean with "No-Key-Encryption" in a
> > small example:
> >
> > Assume Alice wants to send a message to Bob.
> >
> > The message is M = 10101100
> > Alice has a private key A = 11011001
> > Bob has a private key B = 00010111
> >
> > Now, Alice encrypts her message with her private key
> > M XOR A = Ma = 01110101
> >
> > and sends Ma to Bob. Bob can't decrypt the message, but he can
> > encrypt it again using his key
> > Ma XOR B = Mab = 01100010
> >
> > Now Bob sends Mab back to Alice. She decrypts it with her key A
> > Mab XOR A = Mb = 10111011
> >
> > and again sends it to Bob who is now able to decrypt the Message
> > with his key
> > M = Mb XOR B = 10101100
> >
[...]
> The reason your system works is that the combining operation
> is associative,
I think it's a little subtler. We can build the scheme
from an invertible associative operation, call it *, as:
----- k1 * x ----->
<-- k1 * x * k2 ----
----- x * k2 ------>
But what we want is somewhat more general: the encryption
functions must commute. (Which is not the same as saying
each encryption function must be a commutative operation
on message and key.)
Let D_k denote the inverse of E_k, then we need:
D_k2(D_k1(E_k2(E_k1(x)))) = x
Applying E_k2 to both sides:
D_k1(E_k2(E_k1(x))) = E_k2(x)
Applying E_k1 to both sides:
E_k2(E_k1(x)) = E_k1(E_k2(x))
> which is also the reason it, and all system like it, are
> trivially useless. Once an opponent has M+Ka and M+Kb
> recovering M is not hard. Given M recovering the keys is
> not hard.
That's certainly true of the XOR scheme Michael Pellaton
presented. It seems not to be true of other encryption
functions, such as:
E_k(x) = x^k mod p
where p is prime and gcd(k, p-1) = 1
Shamir proposed this one for his "Three-Pass Protocol".
(There are a few other subtle points I'll omit.)
Suppose we limit ourselves to the associative operation
case. Does there exist an associative operation "*" such
that the protocol illustrated above is secure? I don't
know.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (David Boothroyd)
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Tue, 30 May 2000 00:24:27 +0000
In article <[EMAIL PROTECTED]>, Andru Luvisi
<[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] (David Boothroyd) writes:
> [snip]
> > It is not a human rights violation. The s.19 certificate states that the
> > Bill complies with all the UK's human rights obligations.
> [snip]
>
> This is not a usenet post. This is a binding contract which you have
> already signed, stating that you must pay me US$1,000,000 on or before
> July 1st 2000.
Very funny.
A section 19 certificate is a statement by the Minister responsible for
the Bill which states whether or not it complies with the European
Convention on Human Rights. This statement is made on the advice of the
government's law officers. The terms of the European Convention are,
of course, those as drafted in the early 1950s and agreed internationally.
One Bill has had a section 19 certificate stating its provisions do not
comply with human rights - the Local Government Bill, due to amendments
carried against the government in the House of Lords.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Is OTP unbreakable?/Station-Station
Date: Mon, 29 May 2000 23:38:36 GMT
Guy Macon wrote:
> [EMAIL PROTECTED] wrote:
[...]
> >Be that as
> >it may, OTP continues to provide the mechanisms for authentication.
> >If you form a check sum (for example) and encrypt it as the end
> >of the message, you use the OTP to produce the authentication
> >that you claim OTP does not provide.
>
> No. If I use any of the standard authentication protocols,
> someone who knows my plaintext but not my key and who can
> intercept my ciphertext and replace it with his own cannot
> send a message that looks like I sent it. In the case of
> checksum followed by OTP encryption, he can. This is the
> classic man-in-the middle attack combined with the classic
> known/chosen plaintext attack. Good security systems resist
> these attacks, singly or in combination. OTP doesn't.
The method presented by ciphermax is flawed, but a one-time
random key does offer provable authentication, and no other
technique does.
In my opinion it is nonsense to say that the OTP is in any
way weak or has some flaw with respect to authentication.
Most presentations of the OTP only address secrecy, and thus
the term OTP has come to denote these secrecy systems. But
the defining characteristic of the OTP is the single use of
a random key. To gain secrecy, use a random key with a
Lattin square combiner. To gain authentication, use it with
a universal hash function.
(The following is repeated from a post of 1999.12.5 because
I'm lazy.)
To achieve what we might call "perfect
authentication" we use a one-time, uniformly
distributed key - just as we use for secrecy, and a
"universal hash function", which is actually a kind
of MAC because its inputs are a message and a key.
Let's call our message space M, our key space K,
and our signature space S. A universal hash
function is a function s=f(m,k) where m is in M, k
in K and s in S, such that for any two messages m1
and m2 in M, the number of keys k in K such that
f(m1,k) = f(m2,k) is exactly |K|/|S|.
Given such a function and assuming k is chosen
independently for each message in such a way that
each element of K is equally likely, the
probability of one attempted forgery containing the
correct signature is at most 1/|S|.
There are, as always, possible implementation
errors that could violate the assumptions upon
which security rests. For example, we would not
want to use the same shared keystream for privacy
and authentication. An attacker might intercept
and block a message containing known plaintext,
compute the privacy key and use it to properly
encrypt and sign a shorter message of his choosing.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: 30 May 2000 00:00:17 -0000
From: lcs Mixmaster Remailer <[EMAIL PROTECTED]>
Subject: Re: encryption without zeros
> One possibility (assuming that the plaintext has no zero bytes): use your
> favorite block algorithm in ECB mode. When you encrypt a block, you check
> if the ciphertext would contain any zero bytes -- if it does, encrypt the
> block again (and repeat until the output doesn't have any zero bytes).
>
> (I tried to work out a similar procedure for another mode, but I cannot come
> up with way which cannot infinite loop, and whose decryption is
> unambiguous...)
Well, the same idea works OK for CBC mode, which is widely used:
C(N) = C(N-1) XOR E(P(N)).
That is, ciphertext block N is the xor of ciphertext block N-1 and the
encryption of plaintext block N.
We know that P(N) has no bytes of zeros in it.
If C(N) comes out with a zero byte, set P(N) = C(N) and run the equation
again. Repeat until C(N) has no zero bytes. As with ECB mode, the
repetition will only be necessary 3% of the time.
For decryption:
P(N) = D(C(N) XOR C(N-1)).
When iterating the decryption, if P(N) has a zero byte, set C(N)=P(N)
and run the equation again.
It's not clear how to do the trick for CFB or OFB though.
(BTW, this iteration-until-it-fits idea was used in Richard Schroeppel's
Hasty Pudding cipher.)
------------------------------
** 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
******************************
