High-speed high-security cryptography: encrypting and authenticating the whole Internet D. J. Bernstein University of Illinois at Chicago wget -m -k -I / \ secspider.cs.ucla.edu cd secspider.cs.ucla.edu awk ’ /GREEN.*GREEN.*GREEN.*Yes/ { split($0,x,//) sub(/<\/TD>/,"",x[5]) print x[5] } ’ ./*--zone.html \ | sort -u | wc -l A brief history of DNSSEC server deployment: 1993.11: DNSSEC design begins. A brief history of DNSSEC server deployment: 1993.11: DNSSEC design begins. 2008.07: Kaminsky announces apocalypse, saves the world. A brief history of DNSSEC server deployment: 1993.11: DNSSEC design begins. 2008.07: Kaminsky announces apocalypse, saves the world. ) New focus on DNSSEC. A brief history of DNSSEC server deployment: 1993.11: DNSSEC design begins. 2008.07: Kaminsky announces apocalypse, saves the world. ) New focus on DNSSEC. 2009.08.09: 941 IP addresses worldwide are running DNSSEC servers. A brief history of DNSSEC server deployment: 1993.11: DNSSEC design begins. 2008.07: Kaminsky announces apocalypse, saves the world. ) New focus on DNSSEC. 2009.08.09: 941 IP addresses worldwide are running DNSSEC servers. 2010.12.24: 2536 IP addresses worldwide are running DNSSEC servers. What is DNSSEC? What is DNSSEC? Is it a lock for the Internet? What is DNSSEC? Is it a lock for the Internet? Or is it more like this? What is DNSSEC? Is it a lock for the Internet? Or is it more like this? Let’s see what DNSSEC can do as an amplification tool for denial-of-service attacks. Make list of DNSSEC domains: ( cd secspider.cs.ucla.edu awk ’ /^Zone / { z = $2 sub(//,"",z) sub(/<\/STRONG>/,"",z) } /GREEN.*GREEN.*GREEN.*Yes/ { split($0,x,//) sub(/<\/TD>/,"",x[5]) print x[5],z,rand() }’ ./*--zone.html ) | sort -k3n \ | awk ’{print $1,$2}’ \ > SERVERS For each domain: Try query, estimate DNSSEC amplification. while read ip z do dig +dnssec +ignore +tries=1 \ +time=1 any "$z" "@$ip" | \ awk -v "z=$z" -v "ip=$ip" ’{ if ($1 != ";;") next if ($2 != "MSG") next if ($3 != "SIZE") next if ($4 != "rcvd:") next est = (22+$5)/(40+length(z)) print est,ip,z }’ done < SERVERS > AMP For each DNSSEC server, find domain estimated to have maximum DNSSEC amplification: sort -nr AMP | awk ’{ if (seen[$2]) next if ($1 < 30) next print $1,$2,$3 seen[$2] = 1 }’ > MAXAMP head -1 MAXAMP wc -l MAXAMP Output: 95.6279 156.154.102.26 fi. 2326 MAXAMP Can that really be true? > 2000 DNSSEC servers around the Internet, each providing > 30 amplification of incoming UDP packets? Can that really be true? > 2000 DNSSEC servers around the Internet, each providing > 30 amplification of incoming UDP packets? Let’s verify this. Choose quiet test machines on two different networks (without egress filters). e.g. Sender: 1.2.3.4. Receiver: 5.6.7.8. Run network-traffic monitors on 1.2.3.4 and 5.6.7.8. On 1.2.3.4, set response address to 5.6.7.8, and send 1 query/second: ifconfig eth0:1 \ 5.6.7.8 \ netmask 255.255.255.255 while read est ip z do dig -b 5.6.7.8 \ +dnssec +ignore +tries=1 \ +time=1 any "$z" "@$ip" done < MAXAMP >/dev/null 2>&1 I sustained 51 amplification of actual network traffic in a US-to-Europe experiment on typical university computers. I sustained 51 amplification of actual network traffic in a US-to-Europe experiment on typical university computers. Attacker sending 10Mbps can trigger 500Mbps flood from the DNSSEC drone pool, taking down typical site. I sustained 51 amplification of actual network traffic in a US-to-Europe experiment on typical university computers. Attacker sending 10Mbps can trigger 500Mbps flood from the DNSSEC drone pool, taking down typical site. Attacker sending 200Mbps can trigger 10Gbps flood, taking down very large site. I sustained 51 amplification of actual network traffic in a US-to-Europe experiment on typical university computers. Attacker sending 10Mbps can trigger 500Mbps flood from the DNSSEC drone pool, taking down typical site. Attacker sending 200Mbps can trigger 10Gbps flood, taking down very large site. Want even more: 100Gbps? Tell people to install DNSSEC! Cryptographic failure patterns Alice and Bob are communicating. Eve is eavesdropping. Alice and Bob have several standard security goals: Confidentiality despite espionage. Maybe Eve wants to acquire data. Integrity despite corruption. Maybe Eve wants to change data. Availability despite sabotage. Maybe Eve wants to destroy data. Failure pattern #1: “The attacker isn’t sniffing our network packets so we’re secure.” Example of this “security”: Typical HTTP user cookies. Failure pattern #1: “The attacker isn’t sniffing our network packets so we’re secure.” Example of this “security”: Typical HTTP user cookies. Failure pattern #2: “The attacker isn’t forging network packets so we’re secure.” Examples of this “security”:  TCP checking IP address.  DNS checking IP address.  New: Tcpcrypt. Failure pattern #2: “The attacker isn’t forging network packets so we’re secure.” Examples of this “security”:  TCP checking IP address.  DNS checking IP address.  New: Tcpcrypt. “Compare this tcpdump output, which appears encrypted : : : with the cleartext packets you would see without tcpcryptd running. : : : Active attacks are much harder as they require listening and modifying network traffic.” Failure pattern #3: “We detect corrupt data so we’re secure.” Failure pattern #3: “We detect corrupt data so we’re secure.” What about confidentiality? DNSSEC encrypts nothing, and broadcasts private DNS names (such as acadmedpa.org.br). dnscurve.org/nsec3walker.html Failure pattern #3: “We detect corrupt data so we’re secure.” What about confidentiality? DNSSEC encrypts nothing, and broadcasts private DNS names (such as acadmedpa.org.br). dnscurve.org/nsec3walker.html What about availability? Eve destroys an SSH connection or an HTTPS connection or a DNSSEC lookup by forging one packet. Eve uses the DNSSEC drones to amplify DDoS attacks. Failure pattern #4: “The attacker doesn’t control these trusted third parties so we’re secure.” Failure pattern #4: “The attacker doesn’t control these trusted third parties so we’re secure.” Are the HTTPS certificate authorities all trustworthy? Failure pattern #4: “The attacker doesn’t control these trusted third parties so we’re secure.” Are the HTTPS certificate authorities all trustworthy? Is the DNS root trustworthy? Failure pattern #5: “We’re cryptographically protecting so we’re secure.” X Failure pattern #5: “We’re cryptographically protecting so we’re secure.” X Is X the complete communication from Alice to Bob, all the way from Alice to Bob? Failure pattern #5: “We’re cryptographically protecting so we’re secure.” X Is X the complete communication from Alice to Bob, all the way from Alice to Bob? Often X doesn’t reach Bob. Failure pattern #5: “We’re cryptographically protecting so we’re secure.” X Is X the complete communication from Alice to Bob, all the way from Alice to Bob? Often X doesn’t reach Bob. Example: Bob views Alice’s web page on his Android phone. Phone asked hotel DNS cache for web server’s address. Eve forged the DNS response! DNS cache checked DNSSEC but the phone didn’t. Often X isn’t Alice’s data. Often X isn’t Alice’s data. “.ORG becomes the first open TLD to sign their zone with DNSSEC : : : Today we reached a significant milestone in our effort to bolster online security for the .ORG community. We are the first open generic Top-Level Domain to successfully sign our zone with Domain Name Security Extensions (DNSSEC). To date, the .ORG zone is the largest domain registry to implement this needed security measure.” What did .org actually sign? 2010.12.25 test: Look up wikipedia.org. The response has a signed statement “There might be names with hashes between hh91kmqm332a7m6egn74ln9afi3fgk84, hheprfsv14o44rv9pgcndkt4thnraomv but we haven’t signed any of those names. Sincerely, .org” Plus an unsigned statement “The wikipedia.org servers are 208.80.152.130, 208.80.152.142, 91.198.174.4.” Often X is horribly incomplete. Often X is horribly incomplete. Example: X is a server address, with a DNSSEC signature. What Alice is sending to Bob are web pages, email, etc. Those aren’t the same as X ! Often X is horribly incomplete. Example: X is a server address, with a DNSSEC signature. What Alice is sending to Bob are web pages, email, etc. Those aren’t the same as X ! Alice can use HTTPS to protect her web pages : : : but then what attack is stopped by DNSSEC? DNSSEC purists criticize HTTPS: “Alice can’t trust her servers.” DNSSEC signers are offline (preferably in guarded rooms). DNSSEC precomputes signatures. DNSSEC doesn’t trust servers. DNSSEC purists criticize HTTPS: “Alice can’t trust her servers.” DNSSEC signers are offline (preferably in guarded rooms). DNSSEC precomputes signatures. DNSSEC doesn’t trust servers. but X is still wrong! Alice’s servers still control all of Alice’s web pages, unless Alice uses PGP. ::: With or without PGP, what attack is stopped by DNSSEC? Interlude: Signatures Are precomputed signatures fundamentally a good idea? 1. They can’t sign answers that are generated dynamically. Those need security too! Interlude: Signatures Are precomputed signatures fundamentally a good idea? 1. They can’t sign answers that are generated dynamically. Those need security too! DNSSEC purists say “Answers should always be static.” Interlude: Signatures Are precomputed signatures fundamentally a good idea? 1. They can’t sign answers that are generated dynamically. Those need security too! DNSSEC purists say “Answers should always be static.” Imagine the web with only statically generated content: no more database integration, no more PHP, no more fun. Interlude: Signatures Are precomputed signatures fundamentally a good idea? 1. They can’t sign answers that are generated dynamically. Those need security too! DNSSEC purists say “Answers should always be static.” Imagine the web with only statically generated content: no more database integration, no more PHP, no more fun. As boring as cr.yp.to. 2. They can’t sign answers to unpredictable questions. Ask DNSSEC for qptidszl.de. Signed response: “There are no DNSSEC names with hashes between : : : and : : : .” 2. They can’t sign answers to unpredictable questions. Ask DNSSEC for qptidszl.de. Signed response: “There are no DNSSEC names with hashes between : : : and : : : .” Attacker downloads hashes of all 457657 DNSSEC names in .de with < 457657 queries. Invert the hashes to find, e.g., wedemotors.de. Software from Ruben Niederhagen checks 1700 billion names/day on a PC with two GTX 295 graphics cards. 3. They need to be stored. Huge deployment problems. 3. They need to be stored. Huge deployment problems. 4. They aren’t fresh. Is an attacker replaying obsolete signed data? 3. They need to be stored. Huge deployment problems. 4. They aren’t fresh. Is an attacker replaying obsolete signed data? If clocks are synchronized then signatures can include expiration times. But frequent re-signing is an administrative disaster. Some DNSSEC suicide examples: 2010.09.02: .us killed itself. 2010.10.07: .be killed itself. More cryptographic failure patterns Failure pattern #6: “We’re using a cryptographic standard so we’re secure.” Examples of this “security”:  DES.  512-bit RSA.  768-bit RSA.  MD5-based certificates. More cryptographic failure patterns Failure pattern #6: “We’re using a cryptographic standard so we’re secure.” Examples of this “security”:  DES.  512-bit RSA.  768-bit RSA.  MD5-based certificates. Fact: By 1996, a few years after the introduction of MD5, prominent cryptographers such as Preneel and Dobbertin were calling for MD5 to be scrapped. Failure pattern #7: “280 operations are infeasible so we’re secure.” Examples of this “security”:  1024-bit RSA.  160-bit ECC. Failure pattern #7: “280 operations are infeasible so we’re secure.” Examples of this “security”:  1024-bit RSA.  160-bit ECC. Is 280 such a big number? Multi-university ECC2K-130 attack is > 10% done. 77 Will be  2 bit operations. Failure pattern #7: “280 operations are infeasible so we’re secure.” Examples of this “security”:  1024-bit RSA.  160-bit ECC. Is 280 such a big number? Multi-university ECC2K-130 attack is > 10% done. 77 Will be  2 bit operations. One GTX 295 graphics card: 69 bit operations/year. > 2 2048 GTX 295 graphics cards: 80 bit operations/year. > 2 Failure pattern #8: “Even if the 80 attacker can do 2 operations, our data isn’t worth that much, so we’re secure.” Failure pattern #8: “Even if the 80 attacker can do 2 operations, our data isn’t worth that much, so we’re secure.” 1. Does the attack cost so much? Radeon 5970; FPGAs; ASICs. Failure pattern #8: “Even if the 80 attacker can do 2 operations, our data isn’t worth that much, so we’re secure.” 1. Does the attack cost so much? Radeon 5970; FPGAs; ASICs. 2. Are you the only target? Can attack many keys at once, spreading costs over those keys: batch NFS, batch ECDL, etc. Failure pattern #8: “Even if the 80 attacker can do 2 operations, our data isn’t worth that much, so we’re secure.” 1. Does the attack cost so much? Radeon 5970; FPGAs; ASICs. 2. Are you the only target? Can attack many keys at once, spreading costs over those keys: batch NFS, batch ECDL, etc. 3. Is the attacker paying? Conficker broke into > 223 PCs. Failure pattern #9: “This is so complicated that it must be secure.” Failure pattern #9: “This is so complicated that it must be secure.” : : : and so complicated that software implementations never get it right. Failure pattern #9: “This is so complicated that it must be secure.” : : : and so complicated that software implementations never get it right. CVE-2009-0265: BIND DNSSEC bug ) Forge DSA-signed data. Failure pattern #9: “This is so complicated that it must be secure.” : : : and so complicated that software implementations never get it right. CVE-2009-0265: BIND DNSSEC bug ) Forge DSA-signed data. CVE-2009-4022: BIND DNSSEC bug ) Forge all data. Failure pattern #9: “This is so complicated that it must be secure.” : : : and so complicated that software implementations never get it right. CVE-2009-0265: BIND DNSSEC bug ) Forge DSA-signed data. CVE-2009-4022: BIND DNSSEC bug ) Forge all data. CVE-2010-0097: BIND DNSSEC bug ) Forge all data. Failure pattern #9: “This is so complicated that it must be secure.” : : : and so complicated that software implementations never get it right. CVE-2009-0265: BIND DNSSEC bug ) Forge DSA-signed data. CVE-2009-4022: BIND DNSSEC bug ) Forge all data. CVE-2010-0097: BIND DNSSEC bug ) Forge all data. CVE-2010-0290: BIND DNSSEC bug ) Forge all data. Failure pattern #10: “Cryptography is valuable so people will deploy it.” Failure pattern #10: “Cryptography is valuable so people will deploy it.” : : : but too slow to be deployed. Google has installed HTTPS and has fully configured it: https://www.google.com encrypts normal text search, news search, etc. But Google doesn’t allow encryption for high-volume data: images, maps, etc. A different approach Focus on security. Assume that crypto is instantaneous. How easily can we deploy high-security cryptography? A different approach Focus on security. Assume that crypto is instantaneous. How easily can we deploy high-security cryptography? It’s safe for the moment to assume that the attacker can’t do 2128 operations and doesn’t have quantum computers. (Future: see pqcrypto.org.) Safe, conservative crypto: Strong 256-bit elliptic curve. No degradation since 1985. What cryptography does for us: Alice encrypts and authenticates a message using her secret key and Bob’s public key. Bob verifies and decrypts a message using his secret key and Alice’s public key. Attacker can’t understand the encrypted message and can’t forge a verifiable message. What cryptography does for us: Alice encrypts and authenticates a packet using her secret key and Bob’s public key. Bob verifies and decrypts a packet using his secret key and Alice’s public key. Attacker can’t understand the encrypted packet and can’t forge a verifiable packet. What cryptography does for us: Alice encrypts and authenticates a packet using her secret key and Bob’s public key. Bob verifies and decrypts a packet using his secret key and Alice’s public key. Attacker can’t understand the encrypted packet and can’t forge a verifiable packet. Split long messages into separately verified packets to improve availability. Put these protected packets inside a TCP connection, as in SSH and HTTPS? No. Much better availability and much better speed: Send packets through UDP. Discard unverifiable packets. Put these protected packets inside a TCP connection, as in SSH and HTTPS? No. Much better availability and much better speed: Send packets through UDP. Discard unverifiable packets. “UDP is unreliable! We want a reliable stream!” No problem: Imitate TCP inside the protected packets. Simple new protocol: CurveCP. How do we protect HTTP? Alice starts with Bob’s URL. Alice knows her own secret key. How does Alice learn Bob’s public key? How do we protect HTTP? Alice starts with Bob’s URL. Alice knows her own secret key. How does Alice learn Bob’s public key? “Nym” case: URL has a key! Recognize magic number 123 in http:// 1238675309.twitter.com and extract key 8675309. (Technical note: Keys are actually longer than this, but still fit into names.) Normal case: URL is http://www.twitter.com. twitter.com DNS server says www.twitter.com CNAME 1238675309.twitter.com. Again extract key 8675309. Long CNAME chains are bad but short chains are okay and very easy to deploy. Normal case: URL is http://www.twitter.com. twitter.com DNS server says www.twitter.com CNAME 1238675309.twitter.com. Again extract key 8675309. Long CNAME chains are bad but short chains are okay and very easy to deploy. CNAME can’t overlap NS. What if URL is http://twitter.com? Answer: twitter.com NS 1238675309.twitter.com. Alice obtains this DNS data for free as part of looking up server address. Alice uses CurveCP to contact Bob’s web server. As fast as HTTP, but secure! Alice obtains this DNS data for free as part of looking up server address. Alice uses CurveCP to contact Bob’s web server. As fast as HTTP, but secure! Simplifying deployment: Bob actually installs a CurveCP forwarder on UDP port 53 talking to his existing HTTP server on TCP port 80. How did Alice talk to twitter.com DNS server? The DNS server also has a DNSCurve public key: twitter.com NS ... Alice obtains this DNS data for free as part of receiving DNS server address from .com server. Alice uses DNSCurve to contact the DNS server. As fast as DNS, but secure! Standard final step: Obtain .com server key from root server. Well-known root key. But now I think it’s better for DNS software to know the keys for .com, .de, etc. Ultra-powerful root is bad. Standard final step: Obtain .com server key from root server. Well-known root key. But now I think it’s better for DNS software to know the keys for .com, .de, etc. Ultra-powerful root is bad. What if .com misbehaves? Easily protect integrity of web pages from the URL 1238675309.twitter.com but availability is harder. Perhaps P2P DNS can help. Summary of deployment cost: Alice installs DNS cache that understands DNSCurve, and installs HTTP proxy that understands CurveCP. These are small and fast and run on her laptop/phone/etc. Bob installs small forwarder and updates his DNS records. Simple, robust, easy to use. No changes to DNS servers, DNS databases, HTTP servers, web browsers, firewalls, etc. Is speed a problem? Wild speculation by Kaminsky: Secure link from Alice’s computer to Bob’s DNS server means “abandoning caching : : : 100 increase in load.” Is speed a problem? Wild speculation by Kaminsky: Secure link from Alice’s computer to Bob’s DNS server means “abandoning caching : : : 100 increase in load.” Reality check: 1. Measured increase: 1.15. Is speed a problem? Wild speculation by Kaminsky: Secure link from Alice’s computer to Bob’s DNS server means “abandoning caching : : : 100 increase in load.” Reality check: 1. Measured increase: 1.15. 2. Big DNS server operators have much higher capacity. Why? Survive DDoS floods! Is speed a problem? Wild speculation by Kaminsky: Secure link from Alice’s computer to Bob’s DNS server means “abandoning caching : : : 100 increase in load.” Reality check: 1. Measured increase: 1.15. 2. Big DNS server operators have much higher capacity. Why? Survive DDoS floods! 3. HTTPS can’t be cached and is much bigger than DNS. What about CPU time? Simple crypto_box API from nacl.cace-project.eu: High-security curve (Curve25519). High-security implementation (e.g., no secret array indices). Extensive code validation. Very high speed: Client and server handle 10000000 new public keys in < 10 minutes on typical CPUs. Each public-key computation is shared by many packets. Post-quantum cryptography: pqcrypto.org Measuring DNSSEC amplification and DNSSEC privacy violations: dnscurve.org/dnssecamp.html dnscurve.org/nsec3walker.html General DNSCurve information: dnscurve.org Installing a DNSCurve forwarder: curvedns.on2it.net New CurveCP mailing list: curvecp-subscribe@ list.cr.yp.to