Cryptography-Digest Digest #606, Volume #13 Thu, 1 Feb 01 19:13:00 EST
Contents:
Re: Recommendations on simplest way to add client/server encryption ("Joseph
Ashwood")
Re: On combining permutations and substitutions in encryption ("Paul Pires")
Re: coincidence (JPeschel)
Re: How good is Diamond2 and Saphire ciphers? (JPeschel)
Re: New checksum algorithm (Sami J. Mäkinen)
Re: How good is Diamond2 and Saphire ciphers? (Rex Stewart)
Re: fast signing (David Hopwood)
----------------------------------------------------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Recommendations on simplest way to add client/server encryption
Date: Thu, 1 Feb 2001 14:14:58 -0800
Crossposted-To: comp.security.misc
"Rob Yampolsky" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Assuming I don't want to get involved with setting up a CA, how much less
> secure is it to embed a symmetric encryption key directly into my client
in this
> case than to embed a public key?
Enormously. For a good example of this take a look at Windows CE, they used
an embedded key to encrypt the passwords of the user(s), that was extracted
cleanly and published, in case you don't know what it is it is "susageP"
(Pegasus spelled backward). On the other hand both netscape and ie publish
the public keys of various CAs along with their browsers, none of these CAs
have had their keys recovered (as long as the CA takes proper precautions).
A deliberate leak is another issue. Since I assume you are in charge of this
project, I suggest you keep the only copy of your private key, if you simply
use it to sign the next level down then there is no risk except that you and
only you leak your key (or chose a bad key). If you want to get overly
paranoid, there's a lot of research regarding key splitting that has been
done, but I doubt you need to go that far.
Joe
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: On combining permutations and substitutions in encryption
Date: Thu, 1 Feb 2001 14:37:39 -0800
Matt Timmermans <[EMAIL PROTECTED]> wrote in message
news:034e6.182708$[EMAIL PROTECTED]...
>
> "Terry Ritter" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > [I wrote]
> > >and was referring to the part where you explicitly said "any attack".
> You
> > >meant "any attack against the internal state",
> >
> > That paragraph specifically refers to brute-force attacks on the
> > keyspace. That would include any attempt to simply step through the
> > internal state, along with any attempt to step through all possible
> > keys. It would not include, for example, some sort of interactive
> > chosen-RNG-state attack, where the output results influence the next
> > choice of RNG state. On the other hand, there might be something we
> > could say about that as well.
>
> So keyspace is allowed... Let me be explicit, then. I'm talking about a
> non-brute force, non-interactive attacks like this: Assuming the RNG used
> in the cipher has a key-size of at most K bits (key bits, not internal-state
> bits), I intercept an encrypted message 3K bits long, and later learn the
> corresponding plaintext.
>
> If I had the key, I could then encrypt the message and verify that it
> matches the ciphertext I intercepted. I don't have the key, though --
> that's what I want. Because the entire encryption algorithm is a
> polynomial-time deterministic function E(k,M), however, I can write a 3-SAT
> problem that captures its inversion, i.e.:
>
> Each key bit is a variable, and all the message bits M and ciphertext bits C
> are constants (because I have them).
Unless I am completely missing Terry's point, you may know M and C but
you have no confidence as to which particular M bit relates to what C bit.
The point is that the transposition breaks the relationship between particular
M's and C's. They may be constants but you don't know how they are
inter-related do you? Wouldn't this complicate things for you? It sure
messes with my head.
Before you roast me here, an admission of ignorance. What's a 3-SAT problem
and where do I find out about SAT solvers?
>So, I construct my 3-SAT problem P
> such that P is satisfiable iff there exists some assignment to the K
> variables for which E(k,M) = C. The size of P can be polynomial in the time
> it takes to encrypt the message, thanks to Cook.
>
> I feed the problem P into my favourite SAT solver, and it gives me a
> satisfying assignment for the K key bits. This assignment is extremely
> likely to be the actual key (even with balanced blocks), because I have 3K
> bits of plaintext.
>
> How feasible is this attack? That depends directly on the capabilities of
> my favourite SAT solver. Today, there aren't any very good ones, but that
> doesn't mean there _can't_ be good ones, and this is the root of the problem
> with "provable security". If you were to prove a super-polynomial lower
> bound on this attack, it would also prove super-polynomial lower bounds for
> 3-SAT solvers, which would also prove P!=NP, because 3-SAT is in NP.
>
> Since P!=NP is unproven, it follows that the security of the cipher rests on
> unproven assumptions.
>
> > > [me again]
> > >"Prejudice" is a belief, and irrelevant, because you do not take
> *provable*
> > >security on faith -- you take it on proof. Please provide one.
> >
> > Uh, how about "the state space is large enough." Q.E.D.
>
> [my snide remark deleted after counting to 10 -- If there are qualities of
> provable security in DT, I actually am *very* interested in finding out what
> they are]
>
> > >I suspect
> > >the hard part will be in defining "any possible attack" in some strange
> way
> > >that suits your purposes.
> >
> > A brute-force attack on keys hardly seems strange.
>
> I refuse to believe that, all this time, you have been limiting your notion
> of "any attack on the keyspace" to brute force. Even stupid ciphers are
> secure against brute force attacks on the key.
>
> > Sorry, but you have misinterpreted the intent, which I think was quite
> > clearly set out with a description of the Input and Output channels to
> > the RNG state.
>
> I still can't see a misinterpretation. In what way does the above attack
> violate these properties? It works using only the message, the plaintext,
> and the presumably documented cipher algorithm.
>
> > My intent was set out in my first paragraph:
> >
> > "It is easy to have a prejudice that a cipher cannot be provably
> > secure. The most difficult part of this might be the implicit
> > understanding of "from any possible attack." But most ciphers have a
> > range of currently-known and most-likely attacks, each of which might
> > be addressed and proven *impractical*, if not absolutely impossible."
>
> If we take this alone, it's OK, but then you confuse me by saying that "the
> most likely attack is against the RNG state", which is a whole class of
> attacks that, I believe, includes the attack I've outlined above.
>
> > Even if one cannot prove everything at once, that does not mean that
> > one cannot prove quite a lot, one thing at a time.
>
> Well, security against linear and differential cryptanalysis can certainly
> be proven for some RNGs and some permutation-generating algorithms. There
> are also certainly RNGs with large internal state and permutation-generating
> algorithms that would not be secure against these attacks.
>
> But linear and differential cryptanalysis are boring -- every new
> non-amateur cipher is proof against these, and security against these
> attacks is not enough to label a cipher as "provably secure" without
> appropriate qualifications.
>
> What other types of attack do you think we might be able to prove security
> against?
>
> > On the other hand, if one could get some sort of proof with respect to
> > the ability to limit the RNG state information exposed through the
> > combiner to the opponent, one might well have an interesting proof.
> > With respect to Dynamic Transposition, the vastly larger amount of RNG
> > information which performs a block permutation obviously cannot all be
> > revealed by that block in any way -- there simply is not enough
> > information in the permuted block to do that. And using any of that
> > information depends first on knowing the correct permutation, which is
> > also not exposed.
>
> Except that the permutation is derived deterministically from the key. No
> matter how big the RNG internal state is, it can only generate 2^K different
> permutations from K key bits. In fact, it can only generate 2^K unique
> sequences of permutations (over multiple blocks) from K key bits. If I
> collect a little more than K known-plaintext bits, there will likely be only
> a single key that could have generated them.
>
> > I see no reason why proof could not be developed. Security proofs do
> > not have to be absolute statements of overall security; they may
> > instead say very specific small things about security in a provable
> > way.
>
> I suppose that's the point -- there is very little we _can_ say today. RSA
> can be shown to be as hard as factoring, but we don't really know how hard
> that is. You can prove against differential/linear, because a cipher
> actually has to have special properties to be susceptible to these attacks.
> You might be able to prove that there are no "weak keys" or that the cipher
> doesn't form a group, but you could do this for lots of other ciphers too.
>
> What else is there? You wouldn't be continuing this thread if you didn't
> think there might be something exciting that you could prove, so what might
> it be? What do you think you could prove about the security of a DT cipher
> that you couldn't prove about Rijndael or Twofish, for example?
>
> [meanwhile...]
>
> > >It would help if you would simply define "complete information hiding".
> It
> > >would then be quite clear whether it was possible or not.
> >
> > Answered in the original:
> >
> > "We assume that the opponent has known plaintext, so any additive
> > combiner like XOR will immediately expose the ciphering sequence,
> > which then could be used to attack the RNG. But if we use a stronger
> > combiner -- for example, a keyed Latin square -- the ciphering
> > sequence is not so exposed. If we study this, we can show that some
> > RNG information is not hidden, but the most obvious information is
> > hidden. That is a clear improvement not anticipated in the
> > literature, so there is nothing to tell us how far that can go."
>
> This still leaves ambiguities in what you mean by "hidden" and "complete".
> At the beginning of this method, I outlined an attack that would allow you
> to completely regenerate the RNG internal state and output, because it
> regenerates the key.
>
> Given that we can't prove a super-polynomial lower bound on that attack,
> because we can't prove that P!=NP, then to have "complete hiding" of the RNG
> state, we have to define the term in a way that does not contradict the
> above attack. We could say that "hidden" means "difficult to regenerate",
> but then, it seems to me that "completely hidden" should mean "demonstrably
> impractical to regenerate", which the above attack refutes.
>
> We could define "completely hidden" as "impractical to regenerate Today",
> but that could simply mean that noone has tried hard enough.
>
> If you would just say "DT hides the RNG state well", then I would be
> inclined to agree. I _know_ you don't sell snake oil, Terry, and that
> balanced mixing thing was nicely done, and I'm sure that if you actually
> implemented a DT cipher that it would be pretty darn secure, but the claims
> you have been making w.r.t. DT, provability, and OTP (at least with the
> language you have been using to make them) seem unfounded.
>
>
>
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Date: 01 Feb 2001 22:43:58 GMT
Subject: Re: coincidence
[EMAIL PROTECTED] writes:
>Mayby someone know how look mathematical formula for (I`m not sure that it
>is the right name for it in english) 'counting coincidence'.
>O sites where I could find it.
>
If what you want is the formula for the Index of Coincidence try:
http://members.fortunecity.com/jpeschel/gillog1.htm
and scroll down about 1/3 of the page.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Date: 01 Feb 2001 23:07:21 GMT
Subject: Re: How good is Diamond2 and Saphire ciphers?
[EMAIL PROTECTED] writes:
>This sounds like something interesting. Can you give me any pointers
>to where I might find a description of this? I'll give Google a go but
>a reccomendation would be appreciated.
How about:
http://cryptography.org/
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
Subject: Re: New checksum algorithm
From: [EMAIL PROTECTED] (Sami J. Mäkinen)
Date: Thu, 01 Feb 2001 22:48:06 GMT
[EMAIL PROTECTED] (Stefan Habenschuss) wrote in
<npke6.162212$[EMAIL PROTECTED]>:
>Suppose you have an input size of six 32-bit values having the
>hash-value c6. Now if you want to find a different input of the same
>size which gives us that value, you only have to do the following:
>- choose 5 random values v1 - v5 and compute the checksum c5 for those 5
>values
>- for your original algorithm just compute:
> v5 = (c6 xor (c5 * 8)) - (c5 div 2^29 + c5 div 2^17)
> for your suggested "improvement" just xor the result above with c5
>As you can see your algorithm is far too linear to provide really good
>and widely usable hash-values. I'm sorry if that wasn't your aim at all,
>anyway. If you use your algorithm only for harmless integrity checks on
>your home computer, it still might be a quite good algorithm.
Thanks a lot for help! You are of course right, it's easy to see.
I tried coding it also. So I really showed off my poor knowledge on these
things (math & logic) but I think I learnt a lot at least and understood
how easily this hash was reversed. Anyway, I'll try to redesign a new
one from a new perspective. Thanks a again.
Regards,
Sami J. Mäkinen / [EMAIL PROTECTED]
------------------------------
From: Rex Stewart <[EMAIL PROTECTED]>
Subject: Re: How good is Diamond2 and Saphire ciphers?
Date: Thu, 01 Feb 2001 23:45:10 GMT
In article <[EMAIL PROTECTED]>,
"Paul Pires" <[EMAIL PROTECTED]> wrote:
>
> Rex Stewart <[EMAIL PROTECTED]> wrote in message
news:95cbqp$4nu$[EMAIL PROTECTED]...
> > Assuming you are talking about ciphers Micheal P. Johnson
> > developed in the early 90's:
> >
> <Snip>
> >
> > Sapphire2
> > It has some similarities to RC4 but with an extra twist that
> > it feeds information from both the plaintext and the cyphertext
> > streams into the system. This allows it to be used repeatedly
> > with a single key, unlike standard stream cyphers.
>
> This sounds like something interesting. Can you give me any pointers
> to where I might find a description of this? I'll give Google a go but
> a reccomendation would be appreciated.
>
> Thanks,
>
> Paul
>
The only lead I can find right now is
http://cypherpunks.venona.com/date/1994/12/msg00507.html
I haven't seen much of his work lately, but in the early 90's
he produced several cyphers Ruby-MarkV, Sapphire2, and Diamond2
are the algorythms I remember best.
Sapphire1 was shown vulnerable to a type of chosen plaintext
attack, and Diamond2 was primarily a speedup to Diamond.
The other two products I couldn't remember earlier were
Qcrypt and Shredder. Qcrypt, like ATBASH, was written
by Mike Johnson.
--
Rex Stewart
PGP Print 9526288F3D0C292D 783D3AB640C2416A
Sent via Deja.com
http://www.deja.com/
------------------------------
Date: Thu, 01 Feb 2001 23:56:01 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: fast signing
=====BEGIN PGP SIGNED MESSAGE=====
Joseph Ashwood wrote:
> "David Hopwood" <[EMAIL PROTECTED]> wrote:
> > Joseph Ashwood wrote:
> > > "Paul Rubin" <[EMAIL PROTECTED]> wrote:
> > > > What is being signed? Web pages? From a web server?
> > >
> > > Just signing the audit log, everytime an audited page access is
> > > attempted an audit entry is generated, and every so often it is
> > > signed (default 16 entries). It's basically so the admin can do
> > > post-mortem analysis.
> >
> > So why can't you just use a larger number than 16, or sign at given time
> > intervals? (The latter is better because if the accesses stop for any
> > reason, the last few entries will still get signed.)
>
> It's only the default that is 16, admins can set it to any value up to
> 2^31-1. There is actually a time-based signing operation happening along
> side this. For heavy sites this is the option I give them right now, set the
> distance between entries to 1000000000, and set the time between entries to
> match their needs. I just want to get beyond that because it requires them
> to do extra configuration.
If I understand the application correctly, the only disadvantage of
signing with a distance between entries greater than 1, is that an attacker
might be able to compromise the host and then tamper with the log entries
before they get written to some kind of append-only storage (for example,
another hopefully-more-secure host, or write-once media, or a
tamper-resistant device). Is that correct?
If it is, then how about the following: queue requests to the server so that
they are only processed after the block of log entries that includes the
request has been signed and written. That way, any audited event that causes
a compromise is guaranteed to leave an entry in the log [*]. This will
introduce some latency, but if you sign every 0.01 seconds, say, then the
added latency will be negligable compared to any network delays. There
would have to be enough memory to store (0.01 seconds + time to write to log)
worth of requests in a queue, of course.
[*] assuming that the compromise occurs only as a result of processing a
request, rather than receiving it.
> > ESIGN is faster than DSA,
>
> I'll look into it. NOTE: brief look "
> NTT has led patent applications (Japan, USA, Canada, UK, France,
> Germany and Italy) on the techniques used in this submission. NTT will
> license any resulting patent in a reasonable and non-discriminatory
> fashion."
Tatsuaki Okamoto, Tetsutaro Kobayashi (NTT Laboratories)
"On the Security of EPOC and TSH-ESIGN,"
Submission to IEEE P1363a
says:
# Nippon Telegraph Telephone Corporation (NTT) has submitted EPOC and
# TSH-ESIGN to IEEE P1363a. Should these submissions be selected for
# inclusion in the IEEE P1363a, NTT hereby declares that it is prepared
# to license its patents, both granted and pending, which are
# necessary to use and/or sell implementations of the above submissions
# to an unrestricted number of applicants on a worldwide, non-exclusive,
# royalty-free basis.
TSH-ESIGN is the same version as submitted to NESSIE. It's extremely
likely that it will be included in P1363a.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOnnwSTkCAxeYt5gVAQHqkAgAwSq1o9XEfKcvCrUUzbBUFGq0OE+3O9On
dGsQoTYmc0++MYRtYt2NdjP8/+S0azDeqzvweGkW8G7Lsmu2xD9Wze4UAR4ZK0I7
4p9cUzoxZgxhb7seNq5UZvt6f7rFd+ttd8tPMBS6nDFV3OzRLanU+2XS38+3uaRs
qXvNVXvdj7Y948jRN6RbjT6k8U5djyugP3Q0k31+5o1NRhRLaoUAwy1TBSiZhcqn
lfA3B0ddNoa02Iol+ULc94QVrGYapVQv+H+K54BUsVbD046nUrxC051YiYX/opuF
R33g8ReqGINQ7M/Uiq0lyHQfhdAcemqcx8IYPtMQlJlsIMCCR2894w==
=hGdM
=====END PGP SIGNATURE=====
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
