Re: the effects of a spy
On Thu, Nov 17, 2005 at 12:10:53PM -0500, John Kelsey wrote: > c. Maybe they just got it wrong. SHA0 and SHA1 demonstrate that this > is all too possible. (It's quite plausible to me that they have very > good tools for analyzing block ciphers, but that they aren't or > weren't sure how to best apply them to hash functions.) SHA-* also look very much like the already existing and public MD4 and MD5... I would be very willing to bet that the NSA's classified hash functions (I assume it has some, though to be honest I have only ever seen information about block ciphers) look nothing like SHA. Perhaps their analysis tools apply well to the ones that they build internally, but did not to an MDx-style hash, and they did not want to release a design based on some clever design technique of theirs that the public didn't know about; when SHA was released, Clipper and the export controls were still in full swing, so it seems pretty plausible that the NSA wanted to limit how many goodies it gave away. -Jack - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Fermat's primality test vs. Miller-Rabin
- Original Message -
From: "Anton Stiglic" <[EMAIL PROTECTED]>
Subject: RE: Fermat's primality test vs. Miller-Rabin
The general consensus is that for 500-bit numbers one needs only 6 MR
tests for 2^{-80} error probability [1]:
My own tests disagreed with this, 512-bits seemed to have a threshhold
around 70 passes for random candidates, I'm thinking you forgot a sieving
step there (which would change the number substantially).
and thus a single test gives ~2^{-13}.
If you just took the exponent 80 and divided it by 6 to get ~13, I don't
think that is the right reasoning. Look at table 4.3 of the Handbook of
applied cryptography: for t = 1 (one iteration) and for a 500-bit
candidate,
we have probability p(X | Y_1) <= 2^-56, which is better than what you
concluded. (X representing the event that the candidate n is composite,
Y_t
representing the event that Miller-Rabin(n, t) declares n to be prime).
The results in table 4.3 and 4.4 of HAC are for randomly (uniform) chosen
candidates, and I think you need to do a basic sieving (don't remeber if
that is necessary, but I think it is). The result is due to the fact that
under these conditions, the strong pseudoprime test does in fact much
better
than 1/4 probability of error ( value of P(Y_t | X) is very low ), this
result is due to Damgard, Landrock and Pomerance, based on earlier work of
Erdos and Pomerance.
I think much of the problem is the way the number is being applied. Giving a
stream of random numbers that have passed a single round of MR you will find
that very close to 50% of them are not prime, this does not mean that it
passes 50% of the numbers (the 2^-80 probability given above is of this
type). In fact it appears that integers fall on a continuum of difficulty
for MR, where some numbers will always fail (easy composites), and other
numbers will always pass (primes). The problem comes when trying to denote
which type of probability you are discussing. What are the odds that a
random 512-bit composite will be detected as composite by MR in one round? I
don't think anyone has dependably answered that question, but the answer is
very different from 1-(probability that MR-* says it's a prime)^-k. Any
discussion needs to be more accurately phrased.
For example, my phrasing is that in the tests that I performed 50% (+/-
experimental noise) of those numbers that passed a single round of MR also
passed 128 rounds, leading me to conclude that 50% of the numbers that
passed a single round of MR are in fact prime. Since each number that passed
a single round was subjected to 127 additional rounds, a number of
additional statistics can be drawn, in particular that of those that failed
at least one round none failed less than 40 rounds, and that few passed less
than 40 rounds. Due to the fact that this was only iterated 65536 times
there is still substantial experimental error available. These pieces of
information combined indicate that for 512-bits it is necessary to have 80
rounds of MR to verify a prime.
Joe
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: "ISAKMP" flaws?
* Peter Gutmann:
>>> I haven't been following the IPSec mailing lists of late -- can anyone
>>> who knows details explain what the issue is?
>>
>>These bugs have been uncovered by a PROTOS-style test suite. Such test
>>suites can only reveal missing checks for boundary conditions, leading to
>>out- of-bounds array accesses and things like that. In other words, trivial
>>implementation errors which can be easily avoided using proper programming
>>tools.
>
> I feel a need to comment on statements like this... at several times
> in the past I've seen people make sweeping generalisation like this,
> "Everyone knows about this security weakness, this { paper | article
> | security alert } isn't { novel | interesting | worth publishing }",
Touché.
> or some variant thereof (in this case "these trivial errors are
> easily avoided").
Of course, the relevance of a bug and how easily it could have been
avoided are completely different matters. I mainly wanted to point
out that there is no new cryptography involved.
> What makes these statements rather unconvincing is that the majority
> of all implementations out there all make these trivial
> easily-avoided errors
They have chosen different trade-offs, focusing on performance,
time-to-market and things like that. It's hard enough to create an
ISAKMP implementation that works at all.
> In this particular case if the problem is so trivial and easily
> avoided, why does almost every implementation (according to the
> security advisory) get it wrong?
How many completely independent implementations are there?
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: "ISAKMP" flaws?
* William Allen Simpson: > Quoting "Photuris: Design Criteria", LNCS, Springer-Verlag, 1999: > > The hallmark of successful Internet protocols is that they are > relatively simple. This aids in analysis of the protocol design, > improves implementation interoperability, and reduces operational > considerations. > > Compare with Photuris [RFC-2522], where undergraduate (Keromytis) and > graduate (Spatscheck, Provos) students independently were able to > complete interoperable implementations (in their spare time) in a > month or so Photuris uses a baroque variable-length integer encoding similar to that of OpenPGP, a clear warning sign. 8-/ The protocol also contains nested containers which may specify conflicting lengths. This is one common source of parser bugs. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: "ISAKMP" flaws?
In message <[EMAIL PROTECTED]>, Paul Hoffman writes: >At 11:20 AM +0100 11/17/05, Florian Weimer wrote: >>These bugs have been uncovered by a PROTOS-style test suite. Such >>test suites can only reveal missing checks for boundary conditions, >>leading to out-of-bounds array accesses and things like that. In >>other words, trivial implementation errors which can be easily avoided >>using proper programming tools. > >Which "proper programming tools" would check for a logic path failure >when a crafted packet includes Subpacket A that is only supposed to >be there when Subpacket B is there, but the packet doesn't include >Subpacket B? There are no programming tools that check for this, or >for related issues: it has to be the implementer who has enough >understanding of the protocol and enough time (and program space) to >code against such issues. Decent test case generators. --Steven M. Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: solving, simplification and factorization of boolean equations
Dear Travis, simplification can be reduced to elimination, which is indeed intractable in the general case (for real-sized problems). (I am assuming that you need to simplify a "big" system; however if you only want to simplify a small SBox, then brute forcing might do.). The standard citation on itnractability is [E. Mayr and A. Meyer. The complexity of the word problem for commutative semigroups. Adv. in Math., 46:305–329, 1982.] or Philippon et al.'s article. A more comprehensive approach can be found in [D. Castro, M. Giusti, J. Heintz, G. Matera, L.M. Pardo. "The hardness of polynomial equation solving". Found. Comput. Math. 3 (2003).]; see also the citations in their Intro). The intractability of elimination is well known at least since Grete Hermann (http://en.wikipedia.org/wiki/Grete_Hermann), and most probably since the end of the 19th century. In my opinion "simplification" is a "means" and not an end, and indeed a very intractable mean. On the other hand, form your email I gather that your end is to solve these equations. In polynomial equation solving, special cases are what counts. There is a lot of debate on what are good options for elimination, today there are different approaches presenting families of algorithms that are efficient on certain "problem instances". Briefly I would classify the options as: 1-rewriting techniques (ie Groebner bases), 2-path-following techniques (e.g., [L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer, New York Berlin Heidelberg, 1998.], [B. Huber, B. Sturmfels, A polyhedral method for solving sparse polynomial systems, Mathematics of Computation 64 (112) (1995).]), 3-numeric techniques (e.g., [W. Rheinboldt, Methods for solving systems of nonlinear equations, vol. 70 of CBMS-NSF Regional Conf. Series in Appl. Math., SIAM, Philadelphia, 1998.), 4-an algorithms family based on flat deformations (e.g., [M. Giusti, K. Haegele, J. Heintz, J.E. Morais, J.L. Monta~na, L.M. Pardo, Lower bounds for Diophantine approximation, J. Pure Appl. Algebra 117,118 (1997)] and its predecessors; see http://tera.medicis.polytechnique.fr) There are also many ad hoc constructions (e.g., in crypto) that can be used on very specific problems. I think this is all. I might be unwittingly omitting some other option. Im sorry if I am. I can only speak for the latter technique (4), in which I have contributed; in fact, together with other coauthors we will be releasing a paper which attacks the problem of polynomial equation solving as applied to public-key schemes based on polynomial equations. I have not analyzed block ciphers, which yeild higher degree equations (as compared to the quadratic equations of typical public-key schemes). I hope that this helps, and feel free to mail me on any other questions. Best, Ariel Travis H. wrote: > Does anyone have any references on how one would go about creating > manipulating the boolean equations that govern symmetric ciphers? > > I know that most of the time ciphers describe an algorithm, often > using tables (S-boxes and E-tables) in lieu of providing equations, > and I'm wondering how one goes about generating the equations for each > bit of the output. > > One thing I've always been curious about is the minimum amount of work > (in terms of a primitive boolean gate such as NAND) necessary to > compute the output values. Could there be tables derived from > equations so cleverly arranged that brute forcing is very simple once > you know the original equations, but their exact structure is not > evident from the tables themselves? > > Once you have some equations, how would you go about simplifying them? > I suspect that finding the simplest form is probably NP-hard, but I'm > not certain and don't quite know where to start reading on the > subject. > -- > http://www.lightconsulting.com/~travis/ -><- > "We already have enough fast, insecure systems." -- Schneier & Ferguson > GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B > > - > The Cryptography Mailing List > Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] > -- I was scared. Petrified. Because (x) hearing voices isn't like catching a cold, you can't get rid of it with lemmon tea (y) it's inside, it is not some naevus, an epidermal blemish you can cover up or cauterise (z) I had no control over it. It was there of its own volition, just stopped in and (zz) I was going bananas. -Tibor Fischer ``The Thought Gang" Ariel Waissbein RESEARCHER CORE SECURITY TECHNOLOGIES http://www.coresecurity.com/corelabs - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: "ISAKMP" flaws?
Florian Weimer wrote: Photuris uses a baroque variable-length integer encoding similar to that of OpenPGP, a clear warning sign. 8-/ On the contrary: + a VERY SIMPLE "variable-length integer encoding", where every number has EXACTLY ONE possible representation (unlike ASN.1 which even the spell-checker wants to replace with assinine). + "similar to that of OpenPGP", the most common Open Source security software of the era, where the code could be easily reused (as it was in the initial implementation). The protocol also contains nested containers which may specify conflicting lengths. This is one common source of parser bugs. On the contrary, where are internal nested containers in the protocol? However, as most things that cross the INTER-net, the packets are encapsulated in UDP, IP, and some media frame, all of which may have their own length. That why there are copious "implementation notes", saying for example: When processing datagrams containing variable size values, the length must be checked against the overall datagram length. An invalid size (too long or short) that causes a poorly coded receiver to abort could be used as a denial of service attack. I remember some observers complaining about the 17 warnings concerning comparing the variable length to the UDP length, saying it cluttered the specification. I remember some implementers cheering about the 17 warnings concerning comparing the variable length to the UDP length, saying it helped clarify the specification as they wrote the code. I defy you to find an INTER-net protocol without RTP/TCP/UDP, IP, and media framing At the time, I only had 17 years of protocol implementation experience. Another decade later, it still seems (to me) one of my better efforts. Again, the ISAKMP flaws were foreseeable and avoidable. And Photuris was written before the existence of ISAKMP. -- William Allen Simpson Key fingerprint = 17 40 5E 67 15 6F 31 26 DD 0D B9 9B 6A 15 2C 32 - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: "ISAKMP" flaws?
Florian Weimer wrote: Photuris uses a baroque variable-length integer encoding similar to that of OpenPGP, a clear warning sign. 8-/ Actually, if one variable-length integer encoding is used instead of 5 other formats in all sorts of strange places, I'd say this is a good sign. Although I didn't originally like the variable-length integer I've seen used, I've come to appreciate how much simpler and thus much more secure it makes the code. The protocol also contains nested containers which may specify conflicting lengths. This is one common source of parser bugs. Containers for things are inevitable. I've found they should be encapsulated in their own protected container, so that bugs do not cross boundaries. Yes, this makes for redundancy and possibly conflict, but wasn't it said that in security programming, we should be precise in what we write out and precise in what we accept? Any conflict - reject it. iang PS: I think it was Dan Bernstein who said that, in opposition to the aphorism "be gentle in what you accept?" - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: "ISAKMP" flaws?
* William Allen Simpson: > Florian Weimer wrote: >> Photuris uses a baroque variable-length integer encoding similar to >> that of OpenPGP, a clear warning sign. 8-/ > > On the contrary: > > + a VERY SIMPLE "variable-length integer encoding", where every number >has EXACTLY ONE possible representation (unlike ASN.1 which even the >spell-checker wants to replace with assinine). > > + "similar to that of OpenPGP", the most common Open Source security >software of the era, where the code could be easily reused (as it >was in the initial implementation). Even back then, the integer encoding was considered to be a mistake. | I concur completely. I once got so fed up with this habit that I | tromped around the office singing, "Every bit is sacred / Every bit | is great / When a bit is wasted / Phil gets quite irate." | | Consider this to be one of the prime things to correct. Personally, | I think that numbers should never (well, hardly ever) be smaller | than 32 bits. (Jon Callas, 1997-08-08) >> The protocol also contains >> nested containers which may specify conflicting lengths. This is one >> common source of parser bugs. >> > On the contrary, where are internal nested containers in the protocol? Variable-length integers within other fields, for example. You can't avoid this phenomenon in its entirety, of course, without sacrificing some of the advantages of a binary encoding. > Again, the ISAKMP flaws were foreseeable and avoidable. And Photuris > was written before the existence of ISAKMP. I like ISAKMP as much as the next guy, but somehow I doubt that simpler protocols necessarily lead to more robust software. Sure, less effort is needed to implement them, but writing robust code still comes at an extra cost. *sigh* - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
