6 ms·

The Factoring Dead: Preparing for the Cryptopocalypse

168 points by oracuk 13y ago

VLM 13y ago
An interesting analogy is post-quantum cryptography which gets to more or less the same place (can't depend on factoring being hard) by somewhat different path. There's a nice wikipedia category for post quantum crypto. http://en.wikipedia.org/wiki/Category:Post-quantum_cryptography http://en.wikipedia.org/wiki/Category:Post-quantum_cryptogra... The slideshow (which I paged thru pretty quickly) seemed to be a good general coverage of the whole situation, followed by great detail of exactly precisely one solution, ECC. There's lattice, hash, and multivariate. That's too bad that the slides were so general and then suddenly laser focused. I realize there's time limits, etc. There are also system based issues. What I mean is, lets say you decide to implement a signing only hash algo as a "replacement" for a pure encryption algo which is now magically broken. Well that requires major system changes to move from an encryption system to a signing system to accomplish the same meat-level goal. Its not as simple as search and replace library names. Which is an example of the old saying that crypto is hard.
- damarquis 13y ago
  The author's argument is that the probability of impact on ECC of this line of research is less than probability of an impact on factoring. Post-quantum cryptography has to avoid ECC since the elliptic curve discrete log problem is easily solved by quantum computers. Regarding the possible solutions other than ECC: There are no hash-based encryption schemes, only hash based signatures. I believe there is little faith in any multivariate scheme to remain secure under serious scrutiny. Many such schemes have been broken. The outlook on lattice cryptography, and some coding theory based schemes is slightly more positive. Apparently ECC has received much more attention and study than either of these.
agl 13y ago
The slide deck has an impressive list of authors, but slide 55 (about TLS and ECC) appears to be misleading without the context of the talk itself. I didn't see the talk, so I don't know what they were aiming at, but ECC works the same in TLS 1.0, 1.1 and 1.2. Hybrid chains (i.e. an ECDSA public key in a certificate, signed by an RSA certificate) work fine too. (Not all implementations of TLS support ECC of course.)
- jingo 13y ago
  Slide 55 http://image.slidesharecdn.com/bhslides-130803155156-phpapp01/95/slide-55-1024.jpg http://image.slidesharecdn.com/bhslides-130803155156-phpapp0...
- tptacek 13y ago
  It's my understanding (again, I endorse this talk but had nothing to do with its preparation) that they addressed this on stage, just for whatever it's worth.
milkshakes 13y ago
pdf (who disables save anyway?): https://media.blackhat.com/us-13/us-13-Stamos-The-Factoring-Dead.pdf https://media.blackhat.com/us-13/us-13-Stamos-The-Factoring-...
blumentopf 13y ago
Regarding DNSSEC, it should be noted that ECDSA was specified in April 2012 (RFC 6605) and resolver support started with Unbound 1.4.17 (May 2012) and BIND 9.9.2 (Oct 2012). So this was very recent and the percentage of resolvers on the Internet which have already upgraded to an ECDSA-enabled release is so small that it is absolutely pointless to use ECDSA with DNSSEC now. Most of the resolvers won't recognize the algorithm and will treat the zone contents as unsigned. Regarding OpenSSL, I tested ECC with S/MIME in 2009 and it turned out to be unsupported. Just tried it again with 1.0.1e and it's still not supported. It works for TLS but the problem is that vendors ship outdated releases: Debian stable comes with 1.0.1 which is good, RHEL comes with 1.0.0 which is not so good (no TLS 1.2), SLES comes with 0.9.8j (even in the recently release SLES 11 SP3) which is very bad. So support for ECC is still very disappointing and far away from being usable in production.
rdl 13y ago
Pluggable crypto algorithms are one of the reasons for a lot of protocols being overly baroque and thus vulnerable (due to implementation flaws), or at least not widely used. This all started due to the export controls in the 1990s -- when you needed to have a US/non-US version anyway, you could then do 10 algorithms. But, if you don't have that concern anymore, it's senseless complexity. IMO the best way to do all of this is to have one (set of) algorithm per major version of protocol. It's fine to change that (by adding new protocol handling) going forward, and potentially to deprecate old versions too, but cipher negotiation/etc. is otherwise madness-making. That, and shitty encodings, are most of the pain I have when working with stuff. (The issue raised here of "ECC should be more widely used" is good, though -- I've been looking at blinded ECC algorithms recently.)
- tptacek 13y ago
  That's a weird conclusion to draw given that negotiated key agreement algorithms are what allows us to swap RSA for ECDSA opportunistically and without jettisoning the rest of the protocol. Maybe this would make more sense if you could describe what was madness-making about cipher negotiation.
  - rdl 13y ago
    It certainly has upsides, but I remember pain when involved in or trying to fix things with diverse algorithms. Maybe the memory of the pain was worse than the pain itself, or the pain was from unrelated causes. Mostly it's "I'm not very good at _____, so I like things to be as simple as possible". JCE implementation (mostly related to scope, era, etc.) -- admittedly, we only needed a non-US JCE for a few specific things, as part of an overcomplicated financial transfer system. PGP/OpenPGP; there were lots of reasons this sucked, but multiple ciphersuites didn't help at all. Free S/WAN was painful too (and really most of IPsec), but it's an example of the higher level problem of "too many layers of indirection and abstraction", not "too many algorithm choices." (Poking at OpenSSL internals as a consumer of the library and trying to get it to work with some hardware shit made me mostly want to die, too, but part of that is my inferior C skills, and other things specific to OpenSSL and not to the overall concept of multiple algorithms) OTR, ecash protocols of various types, etc. which used hardcoded algorithms were comparatively painless. ssh is probably a good counterexample -- relatively flexible choices, although the big shift from v1 to v2 fixed a lot more things than just algorithms.
delinka 13y ago
"Most systems are not designed for cryptographic agility" but even if they were, that's yet another vector for attack. If your software is configurable in some way around cryptography (new algorithms in a shared library, new configuration files describing padding or negotiation methods), the the attacker just has to reconfigure your device. When you distribute those changes, they have to be signed; with a configuration currently supported by the app; which probably involves the weak or broken algorithm you're trying to replace. The Problem® as I see it is one of computational power. Everyone carries mobile devices. Everyone expects their mobile devices to be secure. But everyone appears to be more interested in the perceived speed of their devices. How do we make most algorithms more secure? Larger keys, or some other form of increased work for attackers. That slows down smartphones and now people are having a Bad User Experience™ and well, we can't have that. It seems like every time someone makes security more user-friendly, they necessarily introduce weaknesses into the entire system. I gave up on trying to solve these kinds of problems long ago when I realized I was terrible at it.
- gizmo686 13y ago
  For the most part, the concerns over breaking crypto are related to breaking public key cryptography. Becuase of its relative slowness, public key crypto is generally used for key exchange before the devices start using symetric cryptography. Symetric crypto has its own concerns because we have no theoretical foundation for believing it is secure other than the fact that we have yet to break it. At least RSA is backed by factoring, which we have spent much longer trying to break (and also haven't proven to be secure).
  - damarquis 13y ago
    Nitpick: RSA isn't known to be backed by factoring. More precisely, there is no proof that if textbook-RSA encrypted messages could be decrypted quickly that integer factorization could also be done quickly. (Of course if you can factor integers you can decrypt RSA messages quickly). http://en.wikipedia.org/wiki/RSA_problem http://en.wikipedia.org/wiki/RSA_problem There are encryption schemes where decyption of an encrypted message is provably equivalent to factoring. http://en.wikipedia.org/wiki/Rabin_encryption http://en.wikipedia.org/wiki/Rabin_encryption
wbhart 13y ago
The argument here is approximately this: as solving jigsaw puzzles has been dramatically improved recently, you never know, maybe manufacture of weapons of mass destruction will suddenly get really easy overnight, resulting in an apocalypse. What Joux and others have done is both important and impressive. But it simply isn't the same as breaking secure cryptosystems. The analogy between the two is simply overplayed. Did people have reason to believe that the systems Joux and co. can crack were hard? No, despite not knowing how to crack them. Do people believe that their more secure cousins are hard? Yes, they do.
- tptacek 13y ago
  That's a weird way to put it, because Joux and Barbalescu's DLP work has already threatened some real (but exotic) cryptosystems (haven't they?).
tptacek 13y ago
My name is on this talk, but you should know: not only did I not go to Black Hat to help deliver the talk, but I did zero work on its preparation; this is Javed Samuel and Tom Ritter's talk all the way. How my name came to be on it is a long, boring story.
- poulson 13y ago
  Would you be willing to answer what sort of linear algebra is required in the function field sieve that the talk claims is difficult to parallelize? I write open source parallel linear algebra software [1] and would be happy to contribute. [1] http://libelemental.org http://libelemental.org
  - pbsd 13y ago
    The matrices involved are generally modulo a prime (2 in factorization, a fairly large prime for the discrete logarithm), and very sparse. The latest factorization record, RSA-768, involved finding elements of the nullspace of a 192e6 x 192e6 matrix, with an average of 144 nonzeroes per row.
    - poulson 13y ago
      Interesting. That isn't excessively large for distributed-memory Krylov-subspace eigensolvers (e.g., SLEPc). Do you have a good reference for the current algorithms used? And how large is the nullspace typically? EDIT: I assume this [1] is what you're referring to, which draws from the following algorithms of Coppersmith [2,3]. [1]: http://eprint.iacr.org/2010/006.pdf http://eprint.iacr.org/2010/006.pdf [2]: https://www.sciencedirect.com/science/article/pii/002437959390235G?np=y https://www.sciencedirect.com/science/article/pii/0024379593... [3]: http://thales.doa.fmph.uniba.sk/macaj/skola/seminar/CoppersmithMOC62.pdf http://thales.doa.fmph.uniba.sk/macaj/skola/seminar/Coppersm...
      - pbsd 13y ago
        Yes, that is correct. Generally the block Lanczos variant used in practice is Montgomery's [1], though, not Coppersmith's. Lanczos was popular until a few years ago, as it requires slightly less actual matrix-vector multiplications, but since Wiedemann can be partially distributed it is becoming more desirable. [1] http://link.springer.com/content/pdf/10.1007%2F3-540-49264-X_9.pdf http://link.springer.com/content/pdf/10.1007%2F3-540-49264-X...
beagle3 13y ago
Question for the practitioners: is there a hardware token like the yubikey neo, Openpgp card, gemalto.net etc that can do ECC signing or encryption? In some countries, fips140 hardware is required for legal filings, but I've only found RSA tokens.
beagle3 13y ago
Question for those in the know: have there been any advances on DLP in galois fields generated by primitive polynomials?
pbsd 13y ago
I agree with pushing elliptic curves, but I don't like the way they get there. First, some historical corrections: the first L[1/2] algorithm for either factorization or discrete log was CFRAC, presented by Brillhart and Morrison in 1974 [1]. This was the first time a L[1/2] algorithm was formalized: descriptions of this basic method go back to the 1930s and the work of Lehmer and Powers [2] and Kraitchik. I presume 1979 refers to Adleman's subexponential discrete log paper [3]. 1984 saw Coppersmith's L[1/3] algorithm for discrete logarithms in GF(2^n) [4]. The trick was that, in GF(2^n), the freshman's dream is true: A^2 + B^2 = (A + B)^2. This makes the polynomials we need to check for smoothness much smaller (for appropriately chosen polynomials), so much so that the overall asymptotic running time decreases. Then in 1990 the number field sieve [5] appears for factorization, also at L[1/3]. You'd think that this had something to do with 1984's Coppersmith, right? Wrong. The number field sieve came from independent efforts, started by ElGamal [6], Coppersmith et al [7], and Pollard [8]. So you can see that Coppersmith's GF(2^n) trick never factored into the number field sieve. The function field sieve [9] is, however, a continuation of Coppersmith's effort in fields of small characteristic (e.g., GF(2^n), GF(3^n), etc). There are many improvements over the FFS that I'm going to gloss over now. More recently, this work has been continued by Joux and friends [10,11,12,13], who have basically annihilated sieving for some specific fields, and most of the time is spent on individual logs. Note that even for small characteristic, where such algorithms apply, well-chosen fields will still be fairly secure: for example GF(2^2039) still has about 77 bits of security, similar to RSA-1024. There is no reason to believe that the tricks used by Joux carry over to the integers or GF(p), as the 1984 trick never carried over either. We might see an improvement to integer factorization soon, but I seriously doubt these tricks will be in its origin. My guess is that RSA will get an long overdrawn death like Rivest's other brainchild, RC4. There are plenty of reasons to prefer elliptic curves over finite fields. Elliptic curves are smaller, faster, safer, and shinier. But like the finite field case, there are also classes of curves that are cheaper to attack. Did you know that all elliptic curves over GF(2^n) can be solved in subexponential time [14]? Let's move to NTRU! This kind of scare tactics is unproductive. [1] http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0371800-5/S0025-5718-1975-0371800-5.pdf http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975... [2] http://www.ams.org/journals/bull/1931-37-10/S0002-9904-1931-05271-X/S0002-9904-1931-05271-X.pdf http://www.ams.org/journals/bull/1931-37-10/S0002-9904-1931-... [3] http://cr.yp.to/bib/1979/adleman.html http://cr.yp.to/bib/1979/adleman.html [4] http://www.enseignement.polytechnique.fr/profs/informatique/Francois.Morain/Master1/Crypto/projects/Coppersmith84.pdf http://www.enseignement.polytechnique.fr/profs/informatique/... [5] http://www.iai.uni-bonn.de/~adrian/nfs/lenstra90number.pdf http://www.iai.uni-bonn.de/~adrian/nfs/lenstra90number.pdf [6] http://link.springer.com/chapter/10.1007%2F978-1-4684-4730-9_22 http://link.springer.com/chapter/10.1007%2F978-1-4684-4730-9... [7] http://cr.yp.to/bib/1986/coppersmith.html http://cr.yp.to/bib/1986/coppersmith.html [8] http://link.springer.com/content/pdf/10.1007/BFb0091536.pdf http://link.springer.com/content/pdf/10.1007/BFb0091536.pdf [9] http://cr.yp.to/bib/1994/adleman-ffs.html http://cr.yp.to/bib/1994/adleman-ffs.html [10] http://eprint.iacr.org/2012/720 http://eprint.iacr.org/2012/720 [11] http://eprint.iacr.org/2013/074 http://eprint.iacr.org/2013/074 [12] http://eprint.iacr.org/2013/095 http://eprint.iacr.org/2013/095 [13] http://eprint.iacr.org/2013/400 http://eprint.iacr.org/2013/400 [14] http://eprint.iacr.org/2012/146 http://eprint.iacr.org/2012/146
kybernetikos 13y ago
I learnt a little about ECC to make my bitcoin-key-for-encryption-gravatar-as-key-server proof of concept http://kybernetikos.github.io/VisualSecrecy/ http://kybernetikos.github.io/VisualSecrecy/ I really love the way that you can visualise what is actually going on by drawing lines on a graph. Factoring is much less visual for me. It just seems very fun that you have a private factor, a public point and, when doing encryption, you have a shared point which is a literal point on a curve.
utunga 13y ago
Does this help to explain xKeyScore? If there have been major mathematical advances in the last 6 months what is the chance that mathematicians at NSA made those advances 2 years ago and didn't reveal? (How many good mathematicians know colleagues who 'dissapeared' into a career for the spooks, I certainly know of some). If so , what's the chance that somewhere in the billion dollar budgets they found enough money to turn advances into practical attacks? And if such practical attacks exist, wouldn't that have made it possible to turn a network level tap (such as has been revealed) into a usable 'full take' system that bypasses the 'going dark' problem... given prevalence of RSA based approaches to cryptography on the net today.
ds9 13y ago
Kinda late here, and unqualified to comment on math - just wanted to mention, in case ECC and the others eventually are compromised - there is something to fall back on. The "one time pad" method "has been proven to be impossible to crack if used correctly" (https://en.wikipedia.org/wiki/One-time_pad https://en.wikipedia.org/wiki/One-time_pad). Given a side channel that's secure for the purpose, I expect there could be a software implementation that would be usable indefinitely.
- warmwaffles 13y ago
  Unfortunately it is difficult for the receiver to know the key. I don't know how this would be solved, but it's quite the conundrum.
- tptacek 13y ago
  Most systems that attempt to implement one time pads are just stream ciphers built from crappy random number generators; they're crappier versions of RC4. Real one time pads aren't particularly useful (which is why they're rarely used): they require keys as long as their plaintexts. Schneier calls them "pretty much useless": http://www.schneier.com/crypto-gram-0210.html#7 http://www.schneier.com/crypto-gram-0210.html#7 They are, at any rate, a sturdy indicator of snake oil crypto.
- oracuk 13y ago
  If you are an organisation with deep pockets (nation state) and are willing to send trusted (armed, diplomatic) couriers to every end point you want to talk securely with (embassies) every month then it can be secure but it will definitely be expensive.
helmut_hed 13y ago
Slide 5. Why can no one spell "Appelbaum"?

168 points by oracuk 13y ago

VLM 13y ago

An interesting analogy is post-quantum cryptography which gets to more or less the same place (can't depend on factoring being hard) by somewhat different path. There's a nice wikipedia category for post quantum crypto. http://en.wikipedia.org/wiki/Category:Post-quantum_cryptography http://en.wikipedia.org/wiki/Category:Post-quantum_cryptogra... The slideshow (which I paged thru pretty quickly) seemed to be a good general coverage of the whole situation, followed by great detail of exactly precisely one solution, ECC. There's lattice, hash, and multivariate. That's too bad that the slides were so general and then suddenly laser focused. I realize there's time limits, etc. There are also system based issues. What I mean is, lets say you decide to implement a signing only hash algo as a "replacement" for a pure encryption algo which is now magically broken. Well that requires major system changes to move from an encryption system to a signing system to accomplish the same meat-level goal. Its not as simple as search and replace library names. Which is an example of the old saying that crypto is hard.

damarquis 13y ago
The author's argument is that the probability of impact on ECC of this line of research is less than probability of an impact on factoring. Post-quantum cryptography has to avoid ECC since the elliptic curve discrete log problem is easily solved by quantum computers. Regarding the possible solutions other than ECC: There are no hash-based encryption schemes, only hash based signatures. I believe there is little faith in any multivariate scheme to remain secure under serious scrutiny. Many such schemes have been broken. The outlook on lattice cryptography, and some coding theory based schemes is slightly more positive. Apparently ECC has received much more attention and study than either of these.

agl 13y ago

The slide deck has an impressive list of authors, but slide 55 (about TLS and ECC) appears to be misleading without the context of the talk itself. I didn't see the talk, so I don't know what they were aiming at, but ECC works the same in TLS 1.0, 1.1 and 1.2. Hybrid chains (i.e. an ECDSA public key in a certificate, signed by an RSA certificate) work fine too. (Not all implementations of TLS support ECC of course.)

jingo 13y ago
Slide 55 http://image.slidesharecdn.com/bhslides-130803155156-phpapp01/95/slide-55-1024.jpg http://image.slidesharecdn.com/bhslides-130803155156-phpapp0...
tptacek 13y ago
It's my understanding (again, I endorse this talk but had nothing to do with its preparation) that they addressed this on stage, just for whatever it's worth.

milkshakes 13y ago

pdf (who disables save anyway?): https://media.blackhat.com/us-13/us-13-Stamos-The-Factoring-Dead.pdf https://media.blackhat.com/us-13/us-13-Stamos-The-Factoring-...

blumentopf 13y ago

Regarding DNSSEC, it should be noted that ECDSA was specified in April 2012 (RFC 6605) and resolver support started with Unbound 1.4.17 (May 2012) and BIND 9.9.2 (Oct 2012). So this was very recent and the percentage of resolvers on the Internet which have already upgraded to an ECDSA-enabled release is so small that it is absolutely pointless to use ECDSA with DNSSEC now. Most of the resolvers won't recognize the algorithm and will treat the zone contents as unsigned. Regarding OpenSSL, I tested ECC with S/MIME in 2009 and it turned out to be unsupported. Just tried it again with 1.0.1e and it's still not supported. It works for TLS but the problem is that vendors ship outdated releases: Debian stable comes with 1.0.1 which is good, RHEL comes with 1.0.0 which is not so good (no TLS 1.2), SLES comes with 0.9.8j (even in the recently release SLES 11 SP3) which is very bad. So support for ECC is still very disappointing and far away from being usable in production.

rdl 13y ago

Pluggable crypto algorithms are one of the reasons for a lot of protocols being overly baroque and thus vulnerable (due to implementation flaws), or at least not widely used. This all started due to the export controls in the 1990s -- when you needed to have a US/non-US version anyway, you could then do 10 algorithms. But, if you don't have that concern anymore, it's senseless complexity. IMO the best way to do all of this is to have one (set of) algorithm per major version of protocol. It's fine to change that (by adding new protocol handling) going forward, and potentially to deprecate old versions too, but cipher negotiation/etc. is otherwise madness-making. That, and shitty encodings, are most of the pain I have when working with stuff. (The issue raised here of "ECC should be more widely used" is good, though -- I've been looking at blinded ECC algorithms recently.)

tptacek 13y ago
That's a weird conclusion to draw given that negotiated key agreement algorithms are what allows us to swap RSA for ECDSA opportunistically and without jettisoning the rest of the protocol. Maybe this would make more sense if you could describe what was madness-making about cipher negotiation.
- rdl 13y ago
  It certainly has upsides, but I remember pain when involved in or trying to fix things with diverse algorithms. Maybe the memory of the pain was worse than the pain itself, or the pain was from unrelated causes. Mostly it's "I'm not very good at _____, so I like things to be as simple as possible". JCE implementation (mostly related to scope, era, etc.) -- admittedly, we only needed a non-US JCE for a few specific things, as part of an overcomplicated financial transfer system. PGP/OpenPGP; there were lots of reasons this sucked, but multiple ciphersuites didn't help at all. Free S/WAN was painful too (and really most of IPsec), but it's an example of the higher level problem of "too many layers of indirection and abstraction", not "too many algorithm choices." (Poking at OpenSSL internals as a consumer of the library and trying to get it to work with some hardware shit made me mostly want to die, too, but part of that is my inferior C skills, and other things specific to OpenSSL and not to the overall concept of multiple algorithms) OTR, ecash protocols of various types, etc. which used hardcoded algorithms were comparatively painless. ssh is probably a good counterexample -- relatively flexible choices, although the big shift from v1 to v2 fixed a lot more things than just algorithms.

delinka 13y ago

"Most systems are not designed for cryptographic agility" but even if they were, that's yet another vector for attack. If your software is configurable in some way around cryptography (new algorithms in a shared library, new configuration files describing padding or negotiation methods), the the attacker just has to reconfigure your device. When you distribute those changes, they have to be signed; with a configuration currently supported by the app; which probably involves the weak or broken algorithm you're trying to replace. The Problem® as I see it is one of computational power. Everyone carries mobile devices. Everyone expects their mobile devices to be secure. But everyone appears to be more interested in the perceived speed of their devices. How do we make most algorithms more secure? Larger keys, or some other form of increased work for attackers. That slows down smartphones and now people are having a Bad User Experience™ and well, we can't have that. It seems like every time someone makes security more user-friendly, they necessarily introduce weaknesses into the entire system. I gave up on trying to solve these kinds of problems long ago when I realized I was terrible at it.

gizmo686 13y ago
For the most part, the concerns over breaking crypto are related to breaking public key cryptography. Becuase of its relative slowness, public key crypto is generally used for key exchange before the devices start using symetric cryptography. Symetric crypto has its own concerns because we have no theoretical foundation for believing it is secure other than the fact that we have yet to break it. At least RSA is backed by factoring, which we have spent much longer trying to break (and also haven't proven to be secure).
- damarquis 13y ago
  Nitpick: RSA isn't known to be backed by factoring. More precisely, there is no proof that if textbook-RSA encrypted messages could be decrypted quickly that integer factorization could also be done quickly. (Of course if you can factor integers you can decrypt RSA messages quickly). http://en.wikipedia.org/wiki/RSA_problem http://en.wikipedia.org/wiki/RSA_problem There are encryption schemes where decyption of an encrypted message is provably equivalent to factoring. http://en.wikipedia.org/wiki/Rabin_encryption http://en.wikipedia.org/wiki/Rabin_encryption

wbhart 13y ago

The argument here is approximately this: as solving jigsaw puzzles has been dramatically improved recently, you never know, maybe manufacture of weapons of mass destruction will suddenly get really easy overnight, resulting in an apocalypse. What Joux and others have done is both important and impressive. But it simply isn't the same as breaking secure cryptosystems. The analogy between the two is simply overplayed. Did people have reason to believe that the systems Joux and co. can crack were hard? No, despite not knowing how to crack them. Do people believe that their more secure cousins are hard? Yes, they do.

tptacek 13y ago
That's a weird way to put it, because Joux and Barbalescu's DLP work has already threatened some real (but exotic) cryptosystems (haven't they?).

tptacek 13y ago

My name is on this talk, but you should know: not only did I not go to Black Hat to help deliver the talk, but I did zero work on its preparation; this is Javed Samuel and Tom Ritter's talk all the way. How my name came to be on it is a long, boring story.

poulson 13y ago
Would you be willing to answer what sort of linear algebra is required in the function field sieve that the talk claims is difficult to parallelize? I write open source parallel linear algebra software [1] and would be happy to contribute. [1] http://libelemental.org http://libelemental.org
- pbsd 13y ago
  The matrices involved are generally modulo a prime (2 in factorization, a fairly large prime for the discrete logarithm), and very sparse. The latest factorization record, RSA-768, involved finding elements of the nullspace of a 192e6 x 192e6 matrix, with an average of 144 nonzeroes per row.
  - poulson 13y ago
    Interesting. That isn't excessively large for distributed-memory Krylov-subspace eigensolvers (e.g., SLEPc). Do you have a good reference for the current algorithms used? And how large is the nullspace typically? EDIT: I assume this [1] is what you're referring to, which draws from the following algorithms of Coppersmith [2,3]. [1]: http://eprint.iacr.org/2010/006.pdf http://eprint.iacr.org/2010/006.pdf [2]: https://www.sciencedirect.com/science/article/pii/002437959390235G?np=y https://www.sciencedirect.com/science/article/pii/0024379593... [3]: http://thales.doa.fmph.uniba.sk/macaj/skola/seminar/CoppersmithMOC62.pdf http://thales.doa.fmph.uniba.sk/macaj/skola/seminar/Coppersm...
    - pbsd 13y ago
      Yes, that is correct. Generally the block Lanczos variant used in practice is Montgomery's [1], though, not Coppersmith's. Lanczos was popular until a few years ago, as it requires slightly less actual matrix-vector multiplications, but since Wiedemann can be partially distributed it is becoming more desirable. [1] http://link.springer.com/content/pdf/10.1007%2F3-540-49264-X_9.pdf http://link.springer.com/content/pdf/10.1007%2F3-540-49264-X...

beagle3 13y ago

Question for the practitioners: is there a hardware token like the yubikey neo, Openpgp card, gemalto.net etc that can do ECC signing or encryption? In some countries, fips140 hardware is required for legal filings, but I've only found RSA tokens.

beagle3 13y ago

Question for those in the know: have there been any advances on DLP in galois fields generated by primitive polynomials?

pbsd 13y ago

I agree with pushing elliptic curves, but I don't like the way they get there. First, some historical corrections: the first L[1/2] algorithm for either factorization or discrete log was CFRAC, presented by Brillhart and Morrison in 1974 [1]. This was the first time a L[1/2] algorithm was formalized: descriptions of this basic method go back to the 1930s and the work of Lehmer and Powers [2] and Kraitchik. I presume 1979 refers to Adleman's subexponential discrete log paper [3]. 1984 saw Coppersmith's L[1/3] algorithm for discrete logarithms in GF(2^n) [4]. The trick was that, in GF(2^n), the freshman's dream is true: A^2 + B^2 = (A + B)^2. This makes the polynomials we need to check for smoothness much smaller (for appropriately chosen polynomials), so much so that the overall asymptotic running time decreases. Then in 1990 the number field sieve [5] appears for factorization, also at L[1/3]. You'd think that this had something to do with 1984's Coppersmith, right? Wrong. The number field sieve came from independent efforts, started by ElGamal [6], Coppersmith et al [7], and Pollard [8]. So you can see that Coppersmith's GF(2^n) trick never factored into the number field sieve. The function field sieve [9] is, however, a continuation of Coppersmith's effort in fields of small characteristic (e.g., GF(2^n), GF(3^n), etc). There are many improvements over the FFS that I'm going to gloss over now. More recently, this work has been continued by Joux and friends [10,11,12,13], who have basically annihilated sieving for some specific fields, and most of the time is spent on individual logs. Note that even for small characteristic, where such algorithms apply, well-chosen fields will still be fairly secure: for example GF(2^2039) still has about 77 bits of security, similar to RSA-1024. There is no reason to believe that the tricks used by Joux carry over to the integers or GF(p), as the 1984 trick never carried over either. We might see an improvement to integer factorization soon, but I seriously doubt these tricks will be in its origin. My guess is that RSA will get an long overdrawn death like Rivest's other brainchild, RC4. There are plenty of reasons to prefer elliptic curves over finite fields. Elliptic curves are smaller, faster, safer, and shinier. But like the finite field case, there are also classes of curves that are cheaper to attack. Did you know that all elliptic curves over GF(2^n) can be solved in subexponential time [14]? Let's move to NTRU! This kind of scare tactics is unproductive. [1] http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0371800-5/S0025-5718-1975-0371800-5.pdf http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975... [2] http://www.ams.org/journals/bull/1931-37-10/S0002-9904-1931-05271-X/S0002-9904-1931-05271-X.pdf http://www.ams.org/journals/bull/1931-37-10/S0002-9904-1931-... [3] http://cr.yp.to/bib/1979/adleman.html http://cr.yp.to/bib/1979/adleman.html [4] http://www.enseignement.polytechnique.fr/profs/informatique/Francois.Morain/Master1/Crypto/projects/Coppersmith84.pdf http://www.enseignement.polytechnique.fr/profs/informatique/... [5] http://www.iai.uni-bonn.de/~adrian/nfs/lenstra90number.pdf http://www.iai.uni-bonn.de/~adrian/nfs/lenstra90number.pdf [6] http://link.springer.com/chapter/10.1007%2F978-1-4684-4730-9_22 http://link.springer.com/chapter/10.1007%2F978-1-4684-4730-9... [7] http://cr.yp.to/bib/1986/coppersmith.html http://cr.yp.to/bib/1986/coppersmith.html [8] http://link.springer.com/content/pdf/10.1007/BFb0091536.pdf http://link.springer.com/content/pdf/10.1007/BFb0091536.pdf [9] http://cr.yp.to/bib/1994/adleman-ffs.html http://cr.yp.to/bib/1994/adleman-ffs.html [10] http://eprint.iacr.org/2012/720 http://eprint.iacr.org/2012/720 [11] http://eprint.iacr.org/2013/074 http://eprint.iacr.org/2013/074 [12] http://eprint.iacr.org/2013/095 http://eprint.iacr.org/2013/095 [13] http://eprint.iacr.org/2013/400 http://eprint.iacr.org/2013/400 [14] http://eprint.iacr.org/2012/146 http://eprint.iacr.org/2012/146

kybernetikos 13y ago

I learnt a little about ECC to make my bitcoin-key-for-encryption-gravatar-as-key-server proof of concept http://kybernetikos.github.io/VisualSecrecy/ http://kybernetikos.github.io/VisualSecrecy/ I really love the way that you can visualise what is actually going on by drawing lines on a graph. Factoring is much less visual for me. It just seems very fun that you have a private factor, a public point and, when doing encryption, you have a shared point which is a literal point on a curve.

utunga 13y ago

Does this help to explain xKeyScore? If there have been major mathematical advances in the last 6 months what is the chance that mathematicians at NSA made those advances 2 years ago and didn't reveal? (How many good mathematicians know colleagues who 'dissapeared' into a career for the spooks, I certainly know of some). If so , what's the chance that somewhere in the billion dollar budgets they found enough money to turn advances into practical attacks? And if such practical attacks exist, wouldn't that have made it possible to turn a network level tap (such as has been revealed) into a usable 'full take' system that bypasses the 'going dark' problem... given prevalence of RSA based approaches to cryptography on the net today.

ds9 13y ago

Kinda late here, and unqualified to comment on math - just wanted to mention, in case ECC and the others eventually are compromised - there is something to fall back on. The "one time pad" method "has been proven to be impossible to crack if used correctly" (https://en.wikipedia.org/wiki/One-time_pad https://en.wikipedia.org/wiki/One-time_pad). Given a side channel that's secure for the purpose, I expect there could be a software implementation that would be usable indefinitely.

warmwaffles 13y ago
Unfortunately it is difficult for the receiver to know the key. I don't know how this would be solved, but it's quite the conundrum.
tptacek 13y ago
Most systems that attempt to implement one time pads are just stream ciphers built from crappy random number generators; they're crappier versions of RC4. Real one time pads aren't particularly useful (which is why they're rarely used): they require keys as long as their plaintexts. Schneier calls them "pretty much useless": http://www.schneier.com/crypto-gram-0210.html#7 http://www.schneier.com/crypto-gram-0210.html#7 They are, at any rate, a sturdy indicator of snake oil crypto.
oracuk 13y ago
If you are an organisation with deep pockets (nation state) and are willing to send trusted (armed, diplomatic) couriers to every end point you want to talk securely with (embassies) every month then it can be secure but it will definitely be expensive.

helmut_hed 13y ago

Slide 5. Why can no one spell "Appelbaum"?