November 2011 - tor-dev - lists.torproject.org

[Patch] or/eventdns.c
by Gisle Vanem 09 Nov '11

09 Nov '11

I've made eventdns.c + '-DEVDNS_MAIN' compile and work under Windows / MSVC. Some simple patches: * Use set_socket_nonblocking() instead of the F_SETFL hacks. * Preserve the ret-val from evdns_config_windows_nameservers(). * In main(), call network_init() to call WSAStartup() etc. * Removed 'evdns_resolv_conf_parse(DNS_OPTION_NAMESERVERS, ...' and call evdns_init() instead. This uses 'DNS_OPTIONS_ALL'. Does that really matter? Attached diff-1.txt. (sorry, I'm a Git neophyte). --gv

2 2

SHA-3 isn't looking so hot to me
by Markku-Juhani O. Saarinen 04 Nov '11

04 Nov '11

Watson Ladd: > (HMAC is a bad idea anyway: quadratic security bounds are not the best > possible, we have to use nonces anyway to prevent replay attacks, so > Wegman-Carter is a better idea for better in{faster, more secure}. GCM > would be an example of this.) GCM has quadratic security bounds, not only in the proof but in practice too. Furthermore a 128-bit GCM MAC offers much less than 128-bit security; in this sense it is certainly weaker than, say, MD5-HMAC ! And there are the implementation caveats mentioned already mentioned in the list, including Joux's "forbidden attack" which may indeed be very real in many implementations. GCM also tends to be slow on software. I've been told that GCM was pushed through the NIST standardization process mainly by CISCO who were concerned about the performance of their hardware crypto accelerators (many hash functions are tricky to implement on hardware). There's also the issue of weak keys etc. See http://eprint.iacr.org/2011/202.pdf This came out in ECRYPT II Hash Workshop 2011, 19-20 May 2011, Tallinn, Estonia. The current ECRYPT recommendations take this into account, see section 8.5.5 of "ECRYPT II Yearly Report on Algorithms and Keysizes (2010-2011)" for a brief discussion: http://www.ecrypt.eu.org/documents/D.SPA.17.pdf I should be expanding this work as Niels Ferguson noted in the Redmond Crypto Retreat workshop last August that there's a trivial extension of this attack that allows arbitrary message modification. Also a significantly faster method for identifying weak AES-GCM keys has been discovered. As a hash function researcher I would personally select SHA-512 with digest truncated to required number of bits as an interim solution. SHA-512/256 tends to be faster than SHA-256 in software. Also it makes sense to implement a single hash core rather than two (SHA-256 and SHA-512 are fundamentally different). This is also in the standards, see: http://csrc.nist.gov/publications/drafts/fips180-4/Draft-FIPS180-4_Feb2011.… Cheers, - markku Dr. Markku-Juhani O. Saarinen <mjos(a)reveresecurity.com>

8 8

Subject: Re: The consequences of key compromise (or the reasons for changing)
by Markku-Juhani O. Saarinen 04 Nov '11

04 Nov '11

From: Jon Callas <joncallas(a)me.com> > People should get off of 80-bit crypto as soon as is reasonably possible. This means RSA 1024, SHA-1, etc. NIST recommended doing this by the end of 2010, but are now holding their nose and saying that 2013 is the real new date. Absolutely agree. The 80-bit figure was apparently adopted by U.S. Government some 25+ years ago (skipjack etc). > This seems basically reasonable to me. No one has yet factored a 768-bit number, let alone a 1K one. 768-bit RSA was factored in 2009 and the authors of that paper conjecture that 1024 bits would be factored "within a decade" and recommend that 1024-bit RSA should be phased out within a couple of years. http://eprint.iacr.org/2010/006.pdf I am certainly doing that with the stuff that I am maintaining. > SHA-1 actually looks safer today than it did in 2005. But still. Moving away is a Good Thing, so long as it doesn't make you do something stupid. Well, after the 2005 Wang-Yin-Yu paper which had a 2^69 attack, there was a claimed 2^52 attack in 2009 which turned out to have a flawed cost evaluation. There has also been talk of a 2^63 attack, but that difference can be put down to attack implementation skill and detail. I was always doubtful whether or not those techniques could be expanded to work against the SHA-2 algorithms. It is also funny that many people talk about SHA-2 as if was a single algorithm; there are actually two quite distinct algorithms, one for (now fading) 32-bit architectures (SHA-224,SHA-256) and one for 64-bit algorithms (SHA-384,SHA-512,SHA-512/224,SHA-512/256). The variants of these two algorithms only differ in the number of output bits and the IV values and hence have a constant speed regardless of their digest size. You can run "openssl speed sha" to see a real-world performance comparison on a particular box. Cheers, - markku Dr. Markku-Juhani O. Saarinen <mjos(a)reveresecurity.com>

2 1

The consequences of key compromise (or the reasons for changing)
by Watson Ladd 04 Nov '11

04 Nov '11

Dear all, Recently Zooko forwarded an email asking why we have to migrate. I am outlining the reasons in this email why I believe Tor needs to use stronger cryptography very soon. Tor currently uses RSA-1024 bit keys for OR public identities and 1024-bit Diffie Hellman for the negotiation of keys protecting circuits. It also uses SHA-1 for a hash in serveral applications, including key fingerprints. When deciding if these are adequate it is necessary to think about what compromise gives an attacker and what it costs to compromise Tor cryptography. We are aiming to protect users from TLAs with ASICs. Directory keys are 3024 bit RSA. Compromising a directory key is sufficient to generate directories containing fake entries, and thus break the anonymityof all users who see the fake directory. In the event of a compromise, Tor would be unusable until a new version is put out with a longer key length and new directory keys. But these are long keys. However, the keys that actually sign the directories are 1024 bits, but rotate every 3 months. OR keys are also 1024 bit RSA. Compromise of an OR key enables impersonation of the OR to an OP. Combined with fun and games with BGP it enables impersonation of an OR to other ORs, which can direct significant traffic to the fake OR. Detection is likely as the real OR will notice various refusals to connect by other OR to whom it is not connected. And if you can break the directory key why bother with ORs. Hidden services are also identified by 1024 bit RSA keys. At the circuit level DH keys are 1024 bits. An attacker who compromises these can read data intended for further down in the circuit. In particular they can determine the rest of a circuit if they are the first node. There is also the issue of keysize. A Tor cell is 512 bytes long. Thisis sufficent for only 4 keys, if we pack them very tightly. Smaller keys could enable fast circuit initiation or other cool tricks we cannot use today. So, how strong or weak are RSA-1024 and DH-1024 currently? We are using DH over F_q* where q = a big prime. For DH the best known algorithm is the index calculus. This attack proceeds in 3 steps. The first step, which can be spread over multiple keys is the collection of relations among a factor base, usually of small primes. The second step, again spread over multiple keys, is solving the linear system of equations from the first step. The third step is fast and key specific: given an element h,and generator g we attempt to factor g^s*h over the factor base. The general number field sieve is a very similar algorithm for factoring. It is more complicated but again relies on finding smooth numbers and factoring them with respect to a factor base of small primes. Currently the complexity of these algorithms is L_n[1/3,\sqrt^3_{\frac{64}{9}}]for GNFS and L_n[1/2,c] for index calculus. (From wikipedia). Sadly the sieving stepscan be done very well on special hardware. TWIRL, a specialized hardwaredevice designed by Adi Shamir and Eran Tromer is believed by Shamir and Tromer to be capable of factoring a 1024-bit RSA key in a year at a cost of $10 million dollars. To break 10 directory keys in 3 months is 10 times as many keys, and 4 times the speed. That will be $400 million dollars. That is half the cost of Golden Shield for a year: an amount of money that is not ludicrous. And such a machine once built can crack the next 10 keys for free. The cost is design and fabrication of this device: power is comparatively cheap. Of course, such a machine would be unsuited to other bit sizes. If the attacker instead decides to find a discrete logarithm base for DH over 1024, then they will have the ability to break DH-1024 fairly quickly. I haven't seen a good estimate for the time it would take to do this, but it will be a bit more. It will not be much more. And it will be a total break: once a factor basis is found discrete logs are very fast. So an adversary can spend more time and still be happy with the results. So it isn't just directory signing that is an issue but the link protocol as well. And $400 million is a lot. But when you are the Golden Shield director and someone says "for $400 million we can break Tor for a long time" that is not entirely out of the picture. As technology for ASIC fabrication gets better, this price drops. As GNFS gets better it also drops. As index calculus gets better it drops. And as Balmol's cost disease drives up the cost and budget of Golden Shields regular activities, the price drops. Sincerely, Watson Ladd

3 2

[idle speculation] Combining bridge partioning and limiting directory trust?
by Watson Ladd 04 Nov '11

04 Nov '11

Dear all, I read arma's blog entry calling for someone to see if limiting zig-zag attacks would harm anonymity. Well, I don't have an answer, but I did notice that we could increase the number of bridge authorities by having each bridge authority take a distinct subset of bridges to hand out, and then implementing a honest forwarder that forwards an email asking for bridges to a bridge authority based on some hash function of the requesting gmail address. Compromising an authority results in those bridges being cut off, but only a subset of users are affected. This also prevents zig-zag attacks: there are no clients who see bridges in two distinct authorities mandate. Unfortunately this only works if bridges are careful not to be listed by multiple authorities. Sincerely, Watson Ladd -- "Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither Liberty nor Safety." -- Benjamin Franklin

1 0

patch to torspec that seperates out the crypto.
by Watson Ladd 03 Nov '11

03 Nov '11

Dear all, Here is a patch that removes crypto cruft from torspec.txt. It does make torspec unusable because we haven't written crypto.txt yet. In the process I noticed a few things I cleaned up, and also noticed that RELAY_EXTEND cells have to be understood by both ORs, which could be an impediment to migration. Sincerely, Watson Ladd

2 1

Leap Seconds
by Watson Ladd 03 Nov '11

03 Nov '11

Dear All, What precisely is the timestamp? Right now it says "number of seconds since the Unix epoch" which leaves open TAI, UTC, or UT1. We probably are using UTC so I should say that, but I just want to make sure. Sincerely, Watson Ladd

1 0

Rewriting tor-spec to be crypto agnostic
by Watson Ladd 03 Nov '11

03 Nov '11

Dear all, I'm busy rewriting tor-spec (well, mangling it) to be crypto agnostic (read: shoving hard choices to later). In the process I am trying to make it a bit clearer. The spec seems to hold open the possibility that nodes not on the two ends of a circuit can send recognized RELAY cells (the role of OPs in processing RELAY cells is also unclear). Is this the case, or is this not supported given that there are no points at which the spec explicitly calls for them to be sent? Sincerely, Watson Ladd

2 1

A concrete proposal for crypto (at least part of it)
by Watson Ladd 02 Nov '11

02 Nov '11

Dear All, Rather then get further sucked into a debate that is producing more heat then light about Wegman-Carter, I've decided to make a concrete proposal for how Tor can better protect its streams from manipulation. Right now Tor encrypts the streams of data from a client to a OR with AES-CTR and no integrity checks. I propose the following: On establishment of a new connection between a client and an OR (using either the Goldman et al paper or ephermental DH) the client and the OR derive a single 16-byte K. The client has an 8 byte counter which starts at 1, the client counter, the OR an 8 byte counter which starts at 0, the OR counter. Each cell from the client to the OR is protected by AES-GCM defined as in the NIST standard, with a 4 byte string "TorC" being used to make our counter 12 bytes. (If you read the standard you will see this is the method for generating nonces recommended). The counter is incremented by 2 each time a packet is sent. Under no circumstances can it go backward. Under no circumstances does an OR or Client accept a packet that reuses a nonce (nonces should be sent along if we make transport unreliable). Under no circumstances are more then 2^64 packets sent. Under no circumstances are packets longer then 2^32 bytes. Following these rules an attacker who sends 2^64 forgery attempts has probability 2^-36 of successfully forging one message. If we limit the attacker to 2 billion forgery attempts (forgery must be online) then the probability of forgery is 2^-68. I think we can live with that. These numbers come from http://cr.yp.to/antiforgery/securitywcs-20050227.pdf. Note that these numbers assume AES is secure, and are theorems if AES is secure. This proposal is independent from the establishment of streams. This proposal eliminates issues relating to an intermediate node flipping bits in an HTTP request, thereby tagging the traffic, amongst other evil things manipulation can do. If we want more performance the evaluation of a polynomial over GF(2^128) can be replaced by GF(2^130-5), or AES could be replaced by xsalsa20, and the nonce lengthened. Sincerely, Watson Ladd --- "Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither Liberty nor Safety." -- Benjamin Franklin

4 5

SHA-3 isn't looking so hot to me (was: Draft sketch document with ideas for future crypto ops)
by Zooko O'Whielacronx 02 Nov '11

02 Nov '11

In reference to: https://lists.torproject.org/pipermail/tor-dev/2011-November/002999.html > FOR A HASH FUNCTION: SHA256, switching to SHA3 in 2012 when it comes > out. It might be worthwhile waiting for SHA3 in most places and > skipping over the SHA256 stage entirely. The AES contest resulted in a cipher that was much faster than 3-DES and probably safer as well. It is looking like the SHA-3 contest will result in a hash function that is slightly slower than SHA-256, and not obviously safer either! There are some details about the performance issue: the most efficient SHA-3 candidates are faster than SHA-256 on large, expensive, powerful x86_64 servers, and they are faster on long messages (more than a couple thousand bytes). This almost certainly doesn't matter to the tor project! (Nor, I suspect, to almost anyone else.) I'm guessing (sorry for my ignorance about these important facts) that tor uses secure hashes in two ways: first as the "nails" holding the crypto together, such as in commitments, key-derivation, HMAC, and so forth, and second to integrity-check the bulk data in chunks that are approximately "packet sized" -- a few thousand bytes. On a powerful x86_64 server for 4096 bytes [1], the most efficient SHA-3 candidate (Blake-256) takes about 33,000 cycles and SHA-256 takes about 73,000. So the difference is about 40,000 CPU cycles. Assuming that all of this is done on a single core of a 3.4 GHz chip, that means SHA-256 takes about 12 microseconds longer to hash this 4096-byte packet. I don't think that makes much of a difference to anyone. You'd have to process data at more than 190,000,000 bytes per second before this would exceed your ability to do it that with SHA-256 on a single one of the 4 cores that come in that chip. Is that a realistic amount of data for a single tor node to process per second in forseeable future? (Honest question: I have no idea if it is although I would guess not.) Anyway, if you *do* want to process more than 190 MBytes/s on a fancy server in the next few years, you can probably just use more than one of its cores. On the other hand, what if someone wants to deploy Tor in a 32-bit ARM CPU such as in a Freedom Box or in a smart phone. When it is doing 4096-byte packets, Blake-256 is actually less efficient than SHA-256 by about 36,000 cycles. Since the chip in that device is running at a slower clock rate (maybe 800 MHz), then it takes 45 microseconds more to hash that 4096-byte packet with Blake-256 than with SHA-256. If you hash those packets with the slower of the two algorithms (Blake-256), you could handle about 25 MBytes/s using 100% of the only CPU in the system. If you used SHA-256 instead you could handle 35 MBytes/s. If you are using say, 90% of that CPU for other tasks. such as playing a game or watching a movie while running Tor in the background, or even playing a movie which is streaming in over Tor live, then this is the difference between being able to process 2.5 MBytes/s (Blake-256) and 3.5 MBytes/s (SHA-256). That seems be a difference that might matter in practice, unlike the performance difference on expensive x86_64 servers. Okay, what about the "not obviously safer" part? I think there was a bit of a panic a few years ago, in the aftermath of Wang Xiaoyun's breakthrough on SHA-1, that someone might suddenly figure out a way to find collisions in SHA-256. This panic spurred the creation of the SHA-3 project. However, it seems like in the intervening years nobody has published any techniques that really threaten the safety of SHA-256, so now I'm personally no longer so confident that SHA-3 candidates like Blake will endure longer before someone finds a fatal flaw in them than SHA-256 will. SHA-256 has endured substantial analysis by experts for about a decade now. Blake and its fellow competitors have had about three years. I'm not saying that I'm confident that SHA-256 will outlast Blake! I'm saying it could go either way. Bottom line: I would probably move ahead toward SHA-256 and let SHA-3 mature for a few extra years before planning to move to that, if I were you. Regards, Zooko [1] http://bench.cr.yp.to/results-hash.html

5 8