Re: [cryptography] What's the state of the art in factorization?
On 23/04/2010 11:57, Paul Crowley wrote: [2] http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf My preferred signature scheme is the second, DDH-based one in the linked paper, since it produces shorter signatures - are there any proposals which improve on that? There is RSA or Rabin using a signature scheme with message recovery. With a public modulus of n bits, and a hash of h bits, signing a message adds only h bits, as long as - the message to sign is at least (n-h) bits and - you do not care about spending a few modular multiplication to recover some (n-h) bits of the message [where few is 17, 2 or 1 for popular public exponents e of 65537, 3, 2] This is standardized by ISO/IEC 9796-2 (which add a few bits of overhead to h, like 16 when n is a multiple of 8). It is used (with a deprecated and not-quite-perfect option set of ISO/IEC 9796-2) in many applications where size matters, in particular EMV Smart Cards, and the European Digital Tachograph. With e=2 and the newer (randomized) schemes of ISO/IEC 9796-2, you get security provably related to factoring or breaking the hash. François Grieu [I suddenly got a batch of old messages, and wonder what is the appropriate list address] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Spy/Counterspy
-- Christoph Gruber If privacy is outlawed, only outlaws will have privacy. Phil Zimmermann Am 10.07.2010 um 12:57 schrieb Jerry Leichter leich...@lrw.com: On Jul 9, 2010, at 1:00 PM, Pawel wrote: Hi, On Apr 27, 2010, at 5:38 AM, Peter Gutmann (alt) pgut001.reflec...@gmail.com wrote: GPS tracking units that you can fit to your car to track where your kids are taking it [T]he sorts of places that'll sell you card skimmers and RFID cloners have started selling miniature GPS jammers that plug into cigarette-lighter sockets on cars In other words these are specifically designed to stop cars from being tracked. (Some of the more sophisticated trackers will fall back to 3G GSM-based tracking via UMTS modems if they lose the GPS signal, it'll be interested to see how long it takes before the jammers are updated to deal with 3G signals as well, hopefully while leaving 2G intact for phonecalls). Just wondering, why wouldn't GPS trackers use 2G to determine the location? And, also, does it even need a cell service subscription for location determination, or is it enough to query the cell towers (through some handshake protocols) to figure out the proximities and coordinates? The 2G stuff wasn't designed to provide location information; that was hacked in (by triangulating information received at multiple towers) after the fact. I don't know that anyone has tried to do it from the receiver side - it seems difficult, and would probably require building specialized receiver modules (expensive). 3G provides location information as a standard service, so it's cheap and easy. The next attack, of course, is to use WiFi base station triangulation. That's widely and cheaply available already, and quite accurate in many areas. (It doesn't work out in the countryside if you're far enough from buildings, but then you don't have to go more than 60 miles or so from NYC to get to areas with no cell service, either.) The signals are much stronger, and you can get location data with much less information, so jamming would be more of a challenge. Still, I expect we'll see that in the spy vs. spy race. I wrote message to Risks - that seems to never have appeared - citing an article about GPS spoofing. (I've included it below.) In the spy vs. spy game, of course, it's much more suspicious if the GPS suddenly stops working than if it shows you've gone to the supermarket. Of course, WiFi (and presumably UMTS equipment, though that might be harder) can also be spoofed. I had an experience - described in another RISKS article - in which WiFi-based location suddenly teleported me from Manhattan to the Riviera - apparently because I was driving past a cruise ship in dock and its on-board WiFi had been sampled while it was in Europe. -- Jerry The BBC reports (http://news.bbc.co.uk/2/hi/science/nature/8533157.stm) on the growing threat of jamming to satellite navigation systems. The fundamental vulnerability of all the systems - GPS, the Russian Glonass, and the European Galileo - is the very low power of the transmissions. (Nice analogy: A satellite puts out less power than a car headlight, illuminating more than a third of the Earth's surface from 20,000 kilometers.) Jammers - which simply overwhelm the satellite signal - are increasingly available on-line. According to the article, low-powered hand-held versions cost less than £100, run for hours on a battery, and can confuse receivers tens of kilometers away. The newer threat is from spoofers, which can project a false location. This still costs thousands, but the price will inevitably come down. A test done in 2008 showed that it was easy to badly spoof ships off the English coast, causing them to read locations anywhere from Ireland to Scandinavia. Beyond simple hacking - someone is quoted saying You can consider GPS a little like computers before the first virus - if I had stood here before then and cried about the risks, you would've asked 'why would anyone bother?'. - among the possible vulnerabilities are to high-value cargo, armored cars, and rental cars tracked by GPS. As we build more and more location-aware services, we are inherently building more false-location-vulnerable services at the same time. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 1280-Bit RSA
Dan: You didn't mention the option of switching to elliptic curves. A 256-bit elliptic curve is probably stronger than 2048-bit RSA [1] while also being more efficient in every way except for CPU cost for verifying signatures or encrypting [2]. I like the Brainpool curves which comes with a better demonstration that they were generated with any possible back door than do the NIST curves [3]. Regards, Zooko [1] http://www.keylength.com/ [2] http://bench.cr.yp.to/results-sign.html [3] http://www.ecc-brainpool.org/download/draft-lochter-pkix-brainpool-ecc-00.txt - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 1280-Bit RSA
On 11-07-2010 01:11, Brandon Enright wrote: On Fri, 9 Jul 2010 21:16:30 -0400 (EDT) Jonathan Thornburg jth...@astro.indiana.edu wrote: The following usenet posting from 1993 provides an interesting bit (no pun itended) of history on RSA key sizes. The key passage is the last paragraph, asserting that 1024-bit keys should be ok (safe from key-factoring attacks) for a few decades. We're currently just under 1.75 decades on from that message. I think the take-home lesson is that forecasting progress in factoring is hard, so it's useful to add a safety margin... This is quite interesting. The post doesn't say but I suspect at the factoring effort was based on using Quadratic Sieve rather than GNFS. The difference in speed for QS versus GNFS starts to really diverge with larger composites. Here's another table: RSA GNFS QS === 256 43.68 43.73 384 52.58 55.62 512 59.84 65.86 664 67.17 76.64 768 71.62 83.40 1024 81.22 98.48 1280 89.46111.96 1536 96.76124.28 2048 109.41 146.44 3072 129.86 184.29 4096 146.49 216.76 8192 195.14 319.63 16384258.83 469.80 32768342.05 688.62 Clearly starting at key sizes of 1024 and greater GNFS starts to really improve over QS. If the 1993 estimate for RSA 1024 was assuming QS then that was roughly equivalent to RSA 1536 today. Even improving the GNFS constant from 1.8 to 1.6 cuts off the equivalent of about 256 bits from the modulus. The only certainty in factoring techniques is that they won't get worse than what we have today. Brandon - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com The exponent can be further lowered from that (somewhere between 1.6 and 1.7) --- RSA-768 took about 2^67 Opteron instructions to complete, and RSA-512 can be done in about 2^54 similar operations (it is in the realm of possibility for a single box over a few days/weeks). Best regards, Samuel Neves - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Spy/Counterspy
On 10 July 2010 11:57, Jerry Leichter leich...@lrw.com wrote: Beyond simple hacking - someone is quoted saying You can consider GPS a little like computers before the first virus - if I had stood here before then and cried about the risks, you would've asked 'why would anyone bother?'. - among the possible vulnerabilities are to high-value cargo, armored cars, and rental cars tracked by GPS. As we build more and more location-aware services, we are inherently building more false-location-vulnerable services at the same time. Most location-aware services should not care whether the location is real or false, for privacy reasons. Agree about the issue of high-value cargo (but I guess they'll just have to use more reliable mechanisms, like maps and their eyes), don't care about rental cars. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Spy/Counterspy
On Jul 11, 2010, at 1:16 PM, Ben Laurie wrote: Beyond simple hacking - someone is quoted saying You can consider GPS a little like computers before the first virus - if I had stood here before then and cried about the risks, you would've asked 'why would anyone bother?'. - among the possible vulnerabilities are to high-value cargo, armored cars, and rental cars tracked by GPS. As we build more and more location-aware services, we are inherently building more false-location-vulnerable services at the same time. Most location-aware services should not care whether the location is real or false, for privacy reasons. Agree about the issue of high-value cargo (but I guess they'll just have to use more reliable mechanisms, like maps and their eyes), don't care about rental cars. I have no clue what most location-aware services will be in a year, much less in five or ten years. Sure, if you think that the dominant role for such services will be targeted advertising to people passing by storefronts, then it makes little difference if the location is wrong, except perhaps to the stores (and hence the viability of such services) if grossly incorrect information becomes commonplace. But if the service is find me the hospital I can get to fastest, given current road conditions, the cost of error may be rather higher. Privacy is an entirely distinct issue. At the least, services in which I compute something from my location and data I've pre-loaded for a reasonably large area - without ever revealing my location to someone else - have no privacy implications at all. (Note that I've described the characteristics of most GPS units sold today.) But it's easy to come up with examples where such a location-aware service becomes dangerously vulnerable - and perhaps dangerous - if it is fed incorrect location information. How much and how often I share my own location information, under what conditions, and what I get in return, are all very much up in the air - though if we don't address them, they will default to fairly precise location information, fairly frequently, with few usage restrictions, for little I want. But the inherent vulnerability to falsified information is an inherent part of coming up with any valuable use of true information, no matter what privacy policies we agree on. -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Location services risks (was: Re: Spy/Counterspy)
Location-based services are already being used for dating services (big surprise here). Mobiles send their location to a server, the server figures out who is near whom, and matches them. There are lots of variants on that. An obvious risk here is that the server is acting as a location oracle, allowing me to triangulate. Or I can fake my location to be my mark's, and see if he is near there. A senator no longer even has to have a wide stance to be caught cruising :) /ji - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Anyone make any sense out of this skype hack announcement?
I got pointed at this, and it is written unclearly enough that I have no idea what to make of it: http://www.enrupt.com/index.php/2010/07/07/skype-biggest-secret-revealed -- Perry E. Metzgerpe...@piermont.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Fw: [IP] DARPA BAA on homomorphic encryption
Begin forwarded message: Date: Sun, 11 Jul 2010 18:11:56 -0400 From: David Farber d...@farber.net To: ip i...@v2.listbox.com Subject: [IP] DARPA BAA on homomorphic encryption There’s a new DARPA BAA on homomorphic encryption: https://www.fbo.gov/utils/view?id=11be1516746ea13def0e82984d39f59b The goal is to create practical implementations of an idea that only recently has been shown to be possible in theory. That a computation could be performed over data that remains in encrypted form throughout the entire computation. In effect, the computer would execute a program without ever being able to discern any of the computed values. The possible applications of this are far reaching. For example, you could let a cloud facility do all of your computing work without any possibility that any of your private information would be divulged. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
