Re: the effects of a spy

2005-11-18 Thread Jack Lloyd
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.

/speculation

-Jack


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Fermat's primality test vs. Miller-Rabin

2005-11-18 Thread Joseph Ashwood
- 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?

2005-11-18 Thread Florian Weimer
* 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?

2005-11-18 Thread Florian Weimer
* 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?

2005-11-18 Thread Steven M. Bellovin
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

2005-11-18 Thread Ariel Waissbein
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?

2005-11-18 Thread 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).



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?

2005-11-18 Thread Ian G

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?

2005-11-18 Thread Florian Weimer
* 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]