Featured Post

Có một Biển Đông trên không gian mạng

Có một Biển Đông trên không gian mạng Thái Dương Mùa hè 2014, giữa lúc người Việt trong nước và hải ngoại đang sôi sục vì Trung Quốc đư...

Wednesday, June 18, 2014

Javascript Crypto Is Useful

In 2014 I wrote my first Javascript crypto library. Since then I've designed and written many such libraries - eight of which are deployed in popular Google products and services. Javascript crypto can help solve many problems, some of which I'm going to discuss in this post.

Some people have strong feelings about Javascript crypto, and with good reason. Writing crypto code in Javascript is difficult, because of the lack of types and the permissive nature of the run-times. You can always shoot yourself in the foot if you don't know what you're doing in any languages, but you don't even hear the shot in Javascript: the run-times don't usually complain, but they just silently give you an incorrect result.

For example, if you have an array x of 10 elements, accessing x[10] or x[11] won't throw an out of bound exception, but return undefined. This behavior is hostile to crypto code, as demonstrated in this neat exploit discovered by Bleichenbacher, the grandfather of many crypto attacks:

  1. Visit http://people.eku.edu/styere/Encrypt/JS-AES.html. This is a Javascript implementation of AES.
  2. Encrypt this string: ưưưưưưưưưưưưưưưư as ASCII.
  3. Decrypt the ciphertext.
  4. XOR each character of the decryption with 0x52.
  5. And the result is the key.

What happened? The program expects ASCII inputs, but we give it Unicode. The function that causes the vulnerability is SubBytes

// do S-Box substitution
function SubBytes(state, Sbox) {
 var i;
 for( i=0; i<16; i++ )
    state[i] = Sbox[ state[i] ];
 return state;
}

The state variable holds the input. If state[i] >= 256, state[i] would become undefined,because Sbox is an array of only 256 elements.

Many libraries have this “type confusion” vulnerability. How do you fix it? First, you need to validate input. If a function accepts a byte array, it should always check input is an array whose elements are bytes. Secondly, you need to minimize type conversions. Instead of accepting strings in one function and big integers or byte arrays in others, we need to use a single type everywhere. Thirdly, instead of plain old array of numbers you should use typed arrays. When a function accepts an Uint8Array it knows that each element of input is a byte, without doing expensive type checks. Finally, you should Closure and annotate variables and parameters with its pseudo types. The Closure compiler will type-check your program and report type mismatch bugs.

After fixing the type problem, Javascript could only be as bad as other languages when it comes to XOR things together. I've seen broken crypto in C, C++, C#, Java, Ruby, Python, or ActionScript, etc. I disbelieve that Javascript crypto is too bad to do anything with it. The language has its annoying flaws, i.e., numbers are stored as floating point in a 52-bit mantissa, broken bitwise shift left, etc., but they only make the task of programming a crypto library a bit more fun and challenging, not riskier.

Most people consider Javascript crypto harmful after reading this article by Matasano Security (disclaimer: I worked at Matasano before joining Google, and I've always been a huge fan of @tqbf, one of the company's founders.) If you haven't go read it, I'll wait. The article has a good point, but many other criticisms are outdated. Javascript now has a secure PRNG. WebCrypto provides many native crypto primitives, including a secure key storage. Guess what do Stanford, Google, and Microsoft have in common? Each has released an open source Javascript crypto library. No other languages have enjoyed this tremendous support.

That said, I totally agree with its main criticism: if you distrust the network or the server, doing Javascript crypto, with the code being loaded directly over that network from that server, makes you vulnerable to active network attackers or the server itself. If the server or the network is considered as adversary in your threat model, don't trust Javascript crypto code delivered from them. This threat model doesn't, however, apply to most applications. For example, as a Chrome extension End-To-End is immune against this threat. Next I’m going to showcase a few applications of Javascript crypto that are safe too.

1. Build crypto clients
Without Javascript crypto you don't have SSH-In-A-Tab, PwdHash, various Bitcoin wallets, etc. Do you have a Chromecast? If you don't, go buy one. It's amazing. Did you know that it uses Javascript crypto to make the out of box setup so easy and yet secure?
We're living in a world dominated by apps, it's easy to forget that instead of installing an app to do something you can visit a website on your favorite browser and get the same thing done instantly, thanks to the power of Javascript.

2. Stay out of scope of PCI DSS

Large scale systems usually process web requests as follows: Browsers <----> Load Balancers <---> Reverse Proxies <---> Frontends <---> Backends. If the requests contain credit card numbers, all intermediate components must comply to the PCI DSS standard, which could be annoying. To keep the load balancers, the reverse proxies or the frontends out of scope by you can use Javascript crypto to encrypt credit card numbers on browsers and only decrypting them on backends.

3. Avoid data leaks

Because many advertisers are slow in upgrading to HTTPS many advertisement serving systems still use clear text HTTP. Despite lack of encryption, these systems collect and transfer tons of personal data. Javascript crypto, served from a HTTPS origin, ensures collected data in motion are safe against interception.

4. Reduce latency

You have a big fat website that takes many seconds to load because it has megabytes of Javascript code. You may want to cache the base code in localStorage, and download only small diffs. This design is, however, vulnerable to cache poisoning attack. If an attacker manages to insert a backdoor to the cached code (by exploiting a XSS, for example) they will have permanent access (see this talk by my colleague Artur Janc for more details). You need to protect the integrity of the cached code by using a digital signature. You sign the code on the server, and use Javascript crypto to verify the signature.

Conclusion: Programming crypto in Javascript is hard, but doable. As usual if you don't know crypto, you should use good libraries developed by professionals. Javascript crypto has many applications, and has received unprecedented support from Stanford, Google, Microsoft and W3C.

Comments from the interweb: Nate Lawson, Brad Hill, Hacker News. This great article explains why it's hard to maintain large code bases written in Javascript or other dynamic languages.

Sunday, June 8, 2014

Google End-To-End

Hôm kia nhóm của tôi phát hành mã nguồn của End-To-End, chương trình mã hóa email mà bọn tôi làm từ hơn một năm nay. Còn rất nhiều việc phải làm trước khi bọn tôi có một phiên bản chính thức, nhưng đi được bước đầu rồi cũng thấy nhẹ nhõm phần nào. Sáng nay đồng nghiệp báo là phần mềm của bọn tôi được nhắc đến trong một bài báo ở trang nhất của tờ New York Times. Trước đó Edward Snowden cũng có nhắc đến. Woohoo!

Đây là phần mềm lớn nhất mà tôi từng tham gia viết. Tôi chịu trách nhiệm thư viện các thuật toán mã hóa. Phần này nhỏ, nhưng mà để viết được tôi cũng phải đọc nhiều sách vở và các bài báo nghiên cứu. Tôi thích những dự án như thế này, vì làm xong thì mình "lời" được một mớ kiến thức mới.

Mặc dù tôi tự tin thư viện của mình sẽ "nâng giá gạo", nhưng mà tôi cũng thấy rất hồi hộp trước ngày phát hành, không chỉ cho phần của tôi mà còn toàn bộ chương trình. Trước giờ tôi toàn đi chọc ngoáy phần mềm của người khác, đây là lần đầu tôi đưa phần mềm của mình ra cho người khác coi. Cũng may là cho đến nay, cũng gần một tuần rồi, nhưng vẫn chưa có ai tìm được lỗ hổng nào cả.

Mới đầu tôi viết cái thư viện một mình, về sau thì tôi thuyết phục được một đồng nghiệp tham gia viết cùng tôi. Ở Google người ta đánh giá cao khả năng lãnh đạo và muốn chứng minh được khả năng này thì cách tốt nhất là thuyết phục được người khác tham gia dự án của mình. Nghĩa là nếu tự mình thiết kế rồi tự mình viết luôn thì không được đánh giá cao bằng mình thiết kế xong rồi để cho người khác làm.

Anh đồng nghiệp tốt nghiệp Stanford hồi tôi còn chưa được sinh ra. Hơn ba chục năm kinh nghiệm. Trên danh nghĩa thì tôi lãnh đạo phần này, nhưng mà tôi thấy mình học được nhiều điều từ anh ấy hơn là ngược lại. Rốt cuộc trong cái thư viện này chỗ nào tâm tối mịt mờ là do tôi viết, còn lại tất cả những ý tưởng hay ho là của ảnh. Tôi nghĩ nếu mà ảnh viết từ đầu chắc có khi còn hay hơn. Hỏi ra mới biết anh ấy là một thành viên trong nhóm cùng với James Gosling tạo ra Java.

Thư viện của bọn tôi triển khai các hệ mật mã dựa trên đường cong elliptic (elliptic curve crypto). Kiến thức toán của tôi ở đây cực kỳ hạn chế. Tôi chỉ biết rằng từ vài chục năm nay elliptic curve là một lĩnh vực nghiên cứu quan trọng bậc nhất của ngành lý thuyết số. Andrew Wiles chứng minh định lý cuối cùng của Fermat bằng cách chứng minh một định lý về các đường cong này. Trong thập niên 80 của thế kỷ trước người ta phát hiện ra hai ứng dụng khác của elliptic curve: phân tích nhân tử số lớn và xây dựng các hệ mã khóa công khai.

Các hệ mã khóa công khai xây dựng trên lý thuyết số đều dựa vào độ khó của hai bài toán: phân tích nhân tử số lớn và tính logarithm rời rạc trên nhóm Abel hữu hạn (discrete log problem). Hệ mã RSA lừng danh dựa trên bài toán thứ nhất, nhưng cho đến nay người ta đã tìm ra các thuật toán cận mũ (sub-exponential, không biết dịch vậy có đúng không?) để giải quyết bài toán này. Do đó nếu muốn an toàn khi sử dụng RSA thì bắt buộc phải sử dụng các bộ khóa có chiều dài cỡ 3000 bit. Vấn đề là muốn tạo ra các bộ khóa như thế thì phải tìm được các số nguyên tố có chiều dài cỡ 1500 bit, nghĩa là có khoảng 450 chữ số. Khi bọn tôi cài đặt thử một thuật toán dựa trên Miller-Rabin thì thấy muốn tìm được chúng phải mất vài chục giây. Bọn tôi không muốn người sử dụng phải chờ lâu như thế.

Cách đây tầm ba mươi năm hai nhà toán học là Miller và Koblitz cùng phát hiện ra rằng các điểm trên đường cong elliptic định nghĩa trên một trường hữu hạn tạo thành một nhóm Abel hữu hạn và do đó có thể dùng chúng để xây dựng các hệ mật mã khóa công khai. Điều lý thú là thuật toán tốt nhất để giải bài toán discrete log trên các nhóm này vẫn có thời gian chạy lũy thừa. Nói cách khác khi sử dụng elliptic curve crypto thì chiều dài khóa sẽ ngắn hơn. Ngoài ra việc tạo ra các bộ khóa trong các hệ mật mã này cũng rất đơn giản: khóa bí mật chỉ là một số ngẫu nhiên còn khóa công khai thì được tạo ra bằng một phép tính đơn giản.

Khi nào có hứng thú tôi sẽ viết chi tiết về các hệ mật mã này. Ai muốn tìm hiểu thì có thể xem qua các cuốn sách sau đây:

* Introduction Mathematical Cryptography Undergraduate Mathematics: cuốn này rất cơ bản, thích hợp cho người mới bắt đầu. Tôi rất thích cuốn này.

A Computational Introduction to Number Theory and Algebra: cuốn này dành cho những ai muốn tìm hiểu sâu hơn về số học và đại số. Tôi bắt đầu đọc cuốn này cách đây bốn năm, đến giờ vẫn chưa đọc hết. Nghĩ đến thấy buồn quá :-(.

Guide to Elliptic Curve Crypto: cuốn này dành cho những ai muốn viết một thư viện như của bọn tôi, cung cấp kiến thức cơ bản và rất nhiều thông tin về cách triển khai các thuật toán và các hệ mã.

Elliptic Curves: Number Theory and Cryptography: cuốn này đi sâu hơn nữa về elliptic curve, hứa hẹn là sẽ giải thích chứng minh của Andrew Wiles! Tôi đang "cày" cuốn này và chỉ mới đọc được đến chương hai vì không hiểu, phải quay lại cuốn NTB ở trên để đọc lại về nhóm, vành và trường.

Tóm lại cho cái bài hết sức lan man này: mọi con đường đều dẫn về toán. Một phần mềm tưởng chẳng có dây mơ rễ má gì nhưng nhìn kỹ mới thấy toàn toán là toán. Không hiểu toán là không làm được. Thế mà hồi đi học đại học tôi cứ thắc mắc tại sao phải học toán? Chắc là do không thấy được ứng dụng của chúng. Tôi nghĩ cách dạy toán tốt chắc hẳn phải là song song giữa lý thuyết và ứng dụng. Cuốn NTB làm rất tốt điều này. Một hai chương lý thuyết xen kẽ với một hai chương ứng dụng.

Tự học toán rất khó, nhưng mà không học toán thì làm gì cũng khó.

Cập nhật: bạn Tho Tung có còm rằng thật ra Miller và Koblitz không phải là người đầu tiên chỉ ra nhóm các điểm trên đường cong elliptic định nghĩa trên một trường hữu hạn tạo thành một nhóm Abel hữu hạn. Tôi đọc paper của Miller thì thấy đúng là như thế thật. Như vậy đóng góp của Miller và Koblitz là ở chỗ chỉ ra rằng bài toán logarithm rời rạc trên nhóm này là khó và do đó có thể sử dụng chúng để làm mật mã.

Cập nhật: anh Duong-Hieu Phan chỉ ra rằng ngoài còn có rất nhiều hệ mã dựa trên mã sửa sai và đặc biệt là Lattice-based Crypto với tấn công và tính an toàn sử dụng rất nhiều lý thuyết Geometry of Numbers từ Minkowski.