Re: [cryptography] Curve25519 OID
On 06-10-2013 18:45, CodesInChaos wrote: There are many details that are not clear to me. Typical Curve25519 usage deviates from typical NIST curve usage in several ways: 1. montgomery form, not weierstrass (conversion probably possible, never looked into details) This is always possible. For curve25519, we have: y^2 = x^3 - 102314837768112 x + 398341948620716521344 ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] no-keyring public
On 25-08-2013 13:38, Alexander Klimov wrote: There was a ECC program from the previous century that worked as you described: the private key was derived solely from the user password. Unfortunately, I cannot recall its name (and I suspect it already vanished from the net since it was not secure due to its use of EC over binary composite field, Weil descent attack), but I guess someone here remembers its name, since at that time it was a rare example of ECC software. The name was Pegwit: http://www.george-barwood.pwp.blueyonder.co.uk/hp/v8/pegwit.htm ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] cryptanalysis of 923-bit ECC?
On 22-06-2012 18:54, Jon Callas wrote: On Jun 22, 2012, at 2:01 AM, James A. Donald wrote: On 2012-06-22 6:21 PM, James A. Donald wrote: Is this merely a case where 973 bits is equivalent to ~60 bits symmetric? As I, not an authority, understand this result, this result is not oops, pairing based cryptography is broken It is oops, pairing based cryptography requires elliptic curves over a slightly larger field than elliptic curve based cryptography does Indeed. So kudos to the Fujitsu guys, and we make the curves bigger. Even 77 bits is really too small for serious work. Not exactly. If the target is ~80-bit security, ~160-bit elliptic curves are still fine, even for pairing-based crypto. The failure there was the choice of the particular *field* and *curve parameters*. Namely, choosing both the characteristic (3) and the embedding degree (6) to be small left it open to faster attacks. Does anyone know what the ratio is for equivalences, either before or after? If you use *ordinary* pairing-friendly curves, it remains basically the same. For example, consider BN curves. They have an embedding degree k = 12. If you want 128-bit security, you choose an elliptic curve over a 256-bit prime field GF(p). This leaves us with the following attack costs: - 2^128 to solve discrete logs over the elliptic curve over the GF(p) (by rho); - 2^128 to solve discrete logs over the 3072-bit finite field GF(p^12) (by number field sieve**). Therefore, for appropriately chosen curves, the key sizes remain similar. ** There are the so-called medium-prime function field sieve attacks, but for large enough primes and small enough extension degrees they don't seem to matter. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] cryptanalysis of 923-bit ECC?
On 20-06-2012 22:12, Jon Callas wrote: Is this merely a case where 973 bits is equivalent to ~60 bits symmetric? If so, what's equivalent to AES-128 and 256? Is there something inherently weak in pairing-friendly curves, like there are in p^n curves? Disclaimer: I'm not an authority either, but here's what I know: Yeah, pretty much. This is a supersingular curve in the field GF(3^97), or roughly 154 bits. Being a pairing-friendly curve with an embedding degree of 6, there is a map from the group of points of an elliptic curve E(GF(3^97)) to the finite field GF((3^97)^6), which is 923 bit long. So we can solve the logarithm wherever it is the most convenient. Now, low characteristic (3 in this case) fields are vulnerable to a specialized index-calculus attack called the function field sieve (FFS). This method has the same asymptotic complexity of the special number field sieve, i.e., L[1/3, (32/9)^(1/3)]. Therefore, 923 bits is not really that much for the FFS, asymptotically speaking; to put it in perspective, a 911-bit integer was factored back in 2006 by the SNFS, and a 1039-bit one in 2007. For pairing-friendly curves to achieve the 128-bit security level, it is a good idea to increase the characteristic to prevent FFS-style attacks, and to increase the embedding degree to something higher than 6. Barreto-Naehrig curves are defined over (large) prime fields, have embedding degree 12, and are generally a good choice for the 128-bit level. 256-bit security requires even larger embedding degrees, on the order of 24 or so. If you really must stick with the crazy GF(3^n) curves, then take a look at the estimates of the folks that broke this curve: http://eprint.iacr.org/2012/042 (this is where the 2^53 figure came from). ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it?
On 02/01/2012 10:32 PM, Jonathan Katz wrote: On Wed, 1 Feb 2012, Nico Williams wrote: On Wed, Feb 1, 2012 at 3:49 AM, Francois Grieu fgr...@gmail.com wrote: The talk does not give much details, and I failed to locate any article with a similar claim. I would find that result truly remarkable, and it is against my intuition. The video you posted does help me with the intuition problem. The idea seems to be to replace the normal arithmetic in SHA-1 with operations from a zero-knowledge scheme such that in the end you get a zero-knowledge proof of the operations that were applied to the input. That makes complete sense to me, even without seeing the details. But maybe I'm just gullible :^) Nico In some sense this is all not very surprising. The Cramer-Damgard paper he cites in his talk describes a zero-knowledge proof for the NP-complete problem of boolean circuit satisfiability. So the only question is to express SHA-1 (plus a check for string equality) as a boolean circuit and then apply their technique. And implement it, of course. =) (Anyone have an estimate as to how many gates such a circuit would have, assuming you are evaluating SHA-1 on a two-block input?) As he says in his talk, the point of the exercise is not to claim any novelty for the resulting protocol, but to explore how efficient these generic techniques can be when applied to circuits of practical interest. Since he appears not to have written up the work, it is unclear what additional optimizations could have been made. There have been recent developments in this area. The work in [1] shows ZK proofs for integer comparison and AES circuits. It is not fast. SHA-1 is (most likely) not going to be faster. [1] Essam Ghadafi, Nigel P. Smart and Bogdan Warinschi. Practical Zero-Knowledge Proofs for Circuit Evaluation. 2009. http://www.springerlink.com/content/c432727520u07573/ ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] MD5 in MACs in SSL
On 13-09-2011 16:16, Ralph Holz wrote: Hi, I'm wondering about the use of MD5 in SSL MACs. We see that quite often here. What is your take on it? Given that SSL includes replay protection for its session keys, it does not seem to give an attacker any useful time window, but am I missing something maybe? Ralph MACs (read: HMAC) tend to rely on the hash function's second preimage resistance; collision resistance is not a very big deal. MD5 should be fine, although not recommended. Samuel Neves ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] New bit-fiddling instructions in Intel's Haswell
On 14-06-2011 13:13, Jack Lloyd wrote: Intel has publicly described the new instructions that will be available in Haswell (their 22nm chip with ETA 2013). It will include integer AVX, and some interesting new bit fiddling instructions for GPRs, including bit-level gather/scatter instructions (pext/pdep), and an unsigned multiply instruction that doesn't set flags which seems intended for modexp. I suspect there are some interesting possibilities with pext/pdep. While it's about 15 years too late to matter, a table-less DES running entirely in registers seems possible. And last year I played around with a Serpent implementation using pshufb for the 4-bit sboxes, but couldn't find a way of doing the linear transformation quickly; doing the sboxes in the xmm registers and the linear operation in GPRs with these might work out, though. Anyone see other ways to use the new instructions in interesting ways, cryptographically speaking? The instruction reference (PDF) is posted on their formum: http://software.intel.com/en-us/forums/showthread.php?t=83399 -Jack ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography I'm actually unhappy that VPSHUFB still doesn't allow 32-byte wide shuffles (each half does its own 16-byte shuffle. It would seem Intel is still unwilling to abandon their 128-bit wide microarchitecture just yet...I'd very much like that Intel adopt the far more powerful PPERM instruction, part of AMD's XOP extensions. It would allow for 6-bit table lookups, which would even allow for AES bruteforce table lookups in a reasonable amount of cycles. The new integer shift instructions are, of course, interesting (I thought to have seen a rotation instruction in there, but apparently it was wishful thinking). Since every shift constant is variable, it allows for faster Salsa20/ChaCha20, but also speeds Threefish/Skein up by performing the various MIX rounds simultaneously. I can see the bit permutation instructions being used to do very fast binary field squaring (a linear operation) --- will probably be much faster than recurring to PCMULCLDQ, which is not too fast (in current hardware, at least). The Post-32nm instructions also contain RDRAND, which gives access to a hardware random bit generator. It would be interesting to see how these bits are being generated. Best regards, Samuel Neves ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
