Tuesday, April 22, 2014

Friday, April 18, 2014

Fairy tales in password hashing with scrypt

Update: the author of scrypt said that he's added a warning on top of scryptenc.h.

TL;DR: scrypt is a password-based key derivation function that is often used as a password hashing scheme. libscrypt is considered the official implementation of scrypt, but it's actually a file encryption API with the scrypt function never exposed directly. If one misuses libscrypt for password hashing they may end up with extremely weak hashes.

Password-based key derivation functions (PBKDF) are algorithms that take a password and some non-secret data (e.g., salt), and output one or more secret keys that can be further used in other crypto constructions. These functions are generally made deliberately slow so as to frustrate brute-force attack or dictionary attack on the input password.

scrypt is considered a state-of-the-art PBKDF, but its most common use is as a password hashing scheme, even though it wasn't originally designed for this purpose. The author of scrypt has never released a standalone library for the scrypt function; he's released only a utility, confusingly named scrypt, that uses the scrypt function to implement an encryption API.

This makes a lot of senses, as scrypt was originally built for Tarsnap, the online file backup service built by the same person. It's also, however, a crypto disaster waiting to happen: if one uses the file encryption API as a password hashing scheme they may end up with extremely weak hashes. Since the introduction of scrypt I've seen a few of such misuses, all of which were made by otherwise competent programmers.

The scrypt encryption API is declared as follows:

/**
 * scryptenc_buf(inbuf, inbuflen, outbuf, passwd, passwdlen,
 *     maxmem, maxmemfrac, maxtime):
 * Encrypt inbuflen bytes from inbuf, writing the resulting inbuflen + 128
 * bytes to outbuf.
 */
int scryptenc_buf(const uint8_t *, size_t, uint8_t *,
    const uint8_t *, size_t, size_t, double, double);

The intended usage of this function is to derive a key from the password using scrypt (with a randomly generated salt,) then use the derived key to encrypt the input buffer. I've found that many people that want to use scrypt as a password hashing function end up using scryptenc_buf.

In the first case the programmer used scryptenc_buf to encrypt an empty string using the input password as the key, and saved the output as the password hash. There's no badness: although the hash isn't compatible with scrypt anymore, it still has the same strength. It went downhill very fast from here though.

The second programmer used the same function, but she encrypted the input password with a static key. Since scryptenc_buf generates a random salt for each invocation, each password is probably encrypted with a unique key (derived from the random salt and the static key,) but it's still pretty bad: if anyone obtains the static key they can recover all passwords from their hashes. The developer knew that encrypting password is a bad idea, but she was confused by the API. After all the hashes looked random. As the saying goes, bad crypto is usually indistinguishable from good crypto.

The third programmer, for some reason that I've forgotten, wanted to use a single salt for all users, so he modified scryptenc_buf as follows:

scryptenc_buf(const uint8_t * inbuf, size_t inbuflen, uint8_t * outbuf, const uint8_t * passwd,
    size_t passwdlen, const uint8_t * salt, size_t saltlen,
    size_t maxmem, double maxmemfrac, double maxtime);

Like the second programmer, he encrypted the input password with a static key. With a static salt, all passwords are encrypted under one single key. The encryption algorithm used in scryptenc_buf is AES in counter mode with a zero IV. Did you spot the vulnerability? It's the classic keystream reuse: knowing a single password leads to the recovery of all passwords from their hashes. If one can register as a user they can recover all passwords. How comes hashing password introduces such a deadly vulnerability? I run out of people to blame.

The last case was a group of Java programmers. One of them wrote a JNI wrapper on top of libscrypt. The wrapper accepted a memcost parameter, which should be the same as \(N\) in the original scrypt paper, but somehow its author wanted it to be \(\log{N}\). When another programmer called this function he passed, however, \(N\), so the actual memcost parameter became super big. This mismatch should be caught easily, as libscrypt would return an error code if it couldn't allocate the required memory. Checking return value for errors seems not to be, however, a popular pattern in the Java world.

As a result no password was hashed, and all stored hashes were a series of zero bytes. Anyone could sign in to anybody else's accounts using any passwords. Fortunately, they brought my consulting team in very early in the development process, and I found the bug before they had any real users. Moral of the story? Always look at the output of your crypto.

If I develop a crypto library, I'll conduct user studies like how they do it in usability research. Give developers the library and ask them to conduct a specific task. Rinse and repeat until nobody would misuse it.

Tuesday, April 15, 2014

Obama is a liar

Theo Google, một công ty của Mỹ, thì đương kim tổng thống Mỹ là một thằng nói láo, ngu dốt, theo đạo Hồi và cả cộng sản. Mà Google chỉ là dựa vào gợi ý của người dùng Internet thôi nhé: đây là những cụm từ xuất hiện nhiều nhất khi người ta muốn mô tả Obama. Không tin thì bạn thử tìm đi. Thấy chưa? Thấy dân Mỹ chửi Obama như chửi con chưa? Thế mà chẳng thấy ai bị bắt gì cả. Lăng mạ như thế này thì còn thể thống gì nữa. Tự do mà không có khuôn khổ thế này thì loạn mất.

Thế mà nước Mỹ vẫn ổn, vẫn giàu mạnh. Một trăm năm mươi năm nay chuyển giao quyền lực không hề đổ một giọt máu, chỉ có tốn nước miếng thôi.

Trong lúc đó... có một ông tên là Trương Duy Nhất viết blog nói về các "Obama của Việt Nam", chưa dám chửi như chửi con, cũng chẳng dám mắng như chủ mắng đầy tớ, chỉ mới nói nhẹ vài tiếng, nhưng cũng đã được tặng vài cuốn lịch xé chơi qua ngày rồi.

Thử tưởng tượng chúng ta có một Edward Snowden của Việt Nam. Anh ấy vừa chôm được một đống tài liệu bí mật, phải làm gì tiếp theo bây giờ? Chẳng có tờ báo trong nước nào dám đăng. Gửi cho báo nước ngoài thì chính phủ sẽ chặn những tờ báo đó, mà dẫu không chặn thì cũng chẳng mấy ai biết mà tìm đọc. Chắc chỉ còn nước cân ký bán hoặc xé chùi đít dần.

Trong khi đó... Washington Post, tờ báo ở sát nhà Obama, đăng liền tù tì những tài liệu do Snowden gửi đến, rồi đoạt luôn giải Pulitzer, giải thưởng báo chí của chính nước Mỹ. Nghe mỉa mai cứ như là báo Nhân Dân được trao giải báo chí quốc gia vì đã phanh phui những phi vụ đàn áp tự do của chính phủ chúng mình.

Tự do ngôn luận là vậy đó. Rất đơn giản, đâu có gì khó hiểu đâu: tôi được quyền nói, anh được quyền nói, ai cũng được quyền nói và không một ai có quyền kiểm duyệt.

Friday, April 11, 2014

An idea to solve the CloudFlare Heartbleed challenge

tl;dr: list of values that if any of them is leaked one can recover the RSA private key: \(p\), \(q\), \(d \mod{(p-1)}\), \(d \mod{(q-1)}\), \(c^d \mod q\), and \(c^d \mod p\), where \(c\ = m^e\) and \(m\) is the premaster secret sent by the client.

I plan to take a look at the challenge this weekend, but it seems that someone has solved it in just a few hours. Very nice work. Anyway here's how I think this challenge could be solved:
1. Exploit the fact that if you know any intermediate values in the Chinese Remainder algorithm, you can recover the private key.
2. Search for these intermediate values in the leaked memory.

The private key will be used in two cases:
a) To decrypt the proposed premaster secret from the client.
b) To sign an ephemeral (EC)DH public key.

In both cases you know the value \(c\) and \(m\) in the equation \(c^d =  m \pmod N\), where \(d\) is the private key, and \(N\) is the modulus. To make it faster \(c^d \pmod N\) is carried out using Chinese Remainder algorithm in which there are two intermediate values \(x_1\) and \(x_2\) that are calculated as follows:
\(c^d = c^{d\mod{q-1}} = x_1 \pmod q\)
\(c^d = c^{d\mod{p-1}} = x_2 \pmod p\)

Note that \((m - x_1)\) is a multiple of \(q\). So you can use \(\gcd(m - x_1, N)\) to obtain \(q\), if you happen to know \(x_1\). Searching for \(x_1\) looks feasible because it's a bignum half the size of the modulus.

Warning: I haven't verified that this actually works. I just come up with the idea while taking a shower.

Update: I've taken a look at the code, and I think this idea should work. OpenSSL indeed uses Chinese Remainder.

static int RSA_eay_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
{
BIGNUM *r1,*m1,*vrfy;
BIGNUM local_dmp1,local_dmq1,local_c,local_r1;
BIGNUM *dmp1,*dmq1,*c,*pr1;
int ret=0;

BN_CTX_start(ctx);
r1 = BN_CTX_get(ctx);
m1 = BN_CTX_get(ctx);
vrfy = BN_CTX_get(ctx);

r1 and m1 are the intermediate values, and they seem to be allocated for every invocation of this function. Their bignum_st structures are re-used from a pool, but the actual values are freshly allocated from the heap, unless I miss something. This is important, because we want these values sitting near the Heartbeat request. Note that if you read this function you may get the impression that p and q are also freshly allocated, but in fact they aren't.

Update: someone pointed out that r1 and m1 will be scrubbed before Heartbeat requests are processed. Too bad :(.

Update: a simple exploit that simply searches for \(p\) in the leaked memory: https://gist.github.com/epixoip/10570627.

Update: you need to protect pre-calculated CRT parameters stored in the private key as well. See http://lekkertech.net/akamai.txt.

Besides \(d\), \(p\), and \(q\) inside the encoded private key there are also two pre-calcuted CRT parameters: \(d_p = d \pmod{p - 1}\) and \(d_q = d \pmod{q - 1}\). If you know \(d_p\) you can recover the private key as follows:
\[
\begin{aligned}
d_p & = d \pmod{p - 1} \\
\rightarrow ed_p & = ed \pmod{p-1} \\
\rightarrow ed_p & = 1 \pmod{p-1}\\
\end{aligned}
\]
That means \(p - 1\) is a divisor of \(ed_p - 1\).

Tuesday, March 4, 2014

Tại sao Việt Nam nên "ôm hôn" Bitcoin

Cập nhật: viết thêm một chút về thanh toán điện tử và cơn sốt Bitcoin ở Silicon Valley.

Việt Nam là một trong 10 nước nhận kiều hối lớn nhất thế giới. Năm 2013 tổng số tiền mà người (gốc) Việt sống và làm việc ở nước ngoài gửi về Việt Nam trong năm 2013 là 11 tỉ USD và dự kiến năm 2014 sẽ tăng 20%.

Vấn đề lớn nhất của kiều hối là phí cao.

Phí thường được chia làm hai: một phần do các công ty chuyển tiền quốc tế như Money Gram thu, phần còn lại là do ngân hàng trong nước thu. Gửi 1.000 USD từ Mỹ về Việt Nam bằng Money Gram mất 16 USD, nhưng tiền về đến Việt Nam sẽ không bị thu phí gì nữa. Còn hình thức gửi qua chuyển khoản ngân hàng thì sẽ phải chịu hai khoản phí: phí của ngân hàng gửi ở nước ngoài và phí của ngân hàng nhận ở Việt Nam. Ví dụ như gửi 1.000 USD với Wells Fargo thì sẽ mất 11 USD và sau đó sẽ phải chịu thêm phí báo có và phí rút USD của ngân hàng trong nước.

Lợi thế của Bitcoin là phí cực thấp.

Nếu gửi bằng Bitcoin (BTC) thì trong đa số trường hợp phí sẽ chưa đến 1 USD. Với mức giá 600 USD/BTC gửi 1000 USD chỉ mất vài xu tiền phí. Nếu một ngày nào đó mỗi BTC được định giá ngang với 10.000 USD thì mức phí mới là 1 USD. Với công thức tính phí hiện tại thì có gửi 1 triệu USD mức phí cũng sẽ chỉ vài chục xu, dẫu gửi từ bất kỳ nơi nào trên thế giới.

Nếu BTC được chấp nhận rộng rãi ở Việt Nam thì người dân Việt Nam sẽ tiết kiệm được từ vài chục đến vài trăm triệu USD tiền phí kiều hối mỗi năm. Người gửi mua BTC ở nước ngoài và gửi trực tiếp cho người nhận trong nước. Người nhận dùng BTC để mua hàng trực tiếp hoặc có thể đổi BTC ra VND hoặc USD qua các ngân hàng và các sàn giao dịch.

Bất lợi lớn nhất của bitcoin là tỉ giá USD/BTC không ổn định. Không ai muốn gửi về nhà 1.000 USD xong ngày hôm sau chỉ còn phân nửa (cũng có khả năng là gửi 500 ngày mai nhận được 1.000, nhưng chắc lúc đó không ai phàn nàn).

Một cách để giảm thiểu thiệt hại là chỉ dùng mạng Bitcoin để chuyển tiền, nhưng không dùng Bitcoin như một loại tiền tệ. Lúc này mạng Bitcoin đóng vai trò tương tự như các hệ thống thanh toán bù trừ (clearing house) hoặc là các mạng chuyển tiền liên ngân hàng như SWIFT, chỉ có điều thời gian thực thi giao dịch ngắn hơn và chi phí thấp hơn rất nhiều.

Người gửi dùng USD để mua BTC, BTC được chuyển qua mạng Bitcoin đến người nhận, người nhận bán BTC để nhận USD ngay lập tức. Hiện tại nếu đã có sẵn tài khoản thì thời gian để thực thi toàn bộ chuỗi giao dịch này tối thiểu là vài phút và tối đa là một giờ. Trong khoảng thời gian này tỉ giá có thể đã thay đổi, nhưng hi vọng là không quá chênh lệch.

Các công ty kiều hối có thể loại bỏ những công ty trung gian như Money Gram bằng cách cho phép người gửi chuyển BTC trực tiếp vào tài khoản của họ. Chuyện này cực dễ, chỉ cần công bố một địa chỉ nhận bitcoin là được. Sau khi nhận được BTC, công ty kiều hối có thể bán ngay trên các sàn giao dịch và chi trả USD lại cho người nhận trong nước. Hoặc họ cũng có thể giữ lại BTC và dùng chúng khi cần phải chuyển tiền ra nước ngoài.

Không chỉ giảm phí kiều hối Bitcoin còn có thể giúp Việt Nam đẩy nhanh sự phát triển của thương mại điện tử nói riêng và các giao dịch không sử dụng tiền mặt nói chung. Việc thiếu một công cụ thanh toán an toàn, nhanh và chi phí thấp là một trong những trở ngại chính của ngành thương mại điện tử Việt Nam. Người mua muốn mua hàng nhưng không thể trả tiền ngay, người bán muốn bán hàng nhưng không thể nhận được tiền ngay.

Hình thức thanh toán phổ biến nhất vẫn chỉ là giao hàng và nhận tiền mặt tại nhà. Điều này ảnh hưởng rất xấu đến trải nghiệm của khách hàng: phải có mặt ở nhà để nhận hàng, phải giữ tiền mặt trong người, mua rồi mà muốn đổi hay trả lại thì không biết sẽ nhận lại tiền như thế nào, v.v. Đối với người bán hàng thì việc thu tiền tại nhà cũng đem đến nhiều hệ lụy: họ phải có một đội ngũ giao hàng và nhận tiền; tiền nhận về phải kiểm đếm, rồi lại đem đi nộp vào ngân hàng; quan trọng hơn hết là họ không thể cung cấp những dịch vụ tự động làm cho trải nghiệm của khách hàng tốt lên và từ đó thu hút được nhiều khách hàng hơn.

Một hình thức thanh toán phổ biến khác nữa là thanh toán qua thẻ ATM nội địa hoặc thẻ tín dụng quốc tế. Vấn đề của hình thức này là chi phí cao, làm đội giá thành sản phẩm lên, mà rồi người phải chịu chính là khách hàng. Việc cung cấp thông tin thẻ cho một bên thứ ba cũng đem đến rủi ro và phiền toái cho khách hàng. Đã có quá nhiều vụ các công ty bị xâm nhập và thẻ tín dụng của hàng triệu khách hàng bị đánh cắp. Nhưng quan trọng hơn hết là không phải ai cũng có tài khoản ngân hàng hoặc thẻ tín dụng. Thành ra cho đến nay Việt Nam vẫn là một xã hội sử dụng tiền mặt là chính, với tất cả những rủi ro và bất tiện của hình thức thanh toán này.

Bitcoin là cơ hội cực tốt để thay đổi tình trạng này. Ai cũng có thể gia nhập mạng Bitcoin chỉ bằng cách tải về một phần mềm trên máy tính hoặc trên điện thoại. Ai cũng có thể nhận và gửi Bitcoin cho bất kỳ người nào khác cũng chỉ bằng một vài thao tác đơn giản.

Bitcoin bảo vệ người bán bằng cách đảm bảo rằng giao dịch chuyển tiền là không thể đảo ngược - một khi đã chuyển rồi thì không có cách nào hủy được, như là việc trao tay tiền mặt. Do chắc chắn sẽ nhận được tiền, nên người bán không cần phải lo ngại về tình trạng gian lận, không cần phải biết quá nhiều thông tin về khách hàng và đặc biệt là không cần phải dựa vào bên thứ ba để thực hiện giao dịch mua bán như thẻ tín dụng. Thành ra chi phí bán hàng sẽ giảm xuống, trải nghiệm của khách hàng sẽ tốt hơn - cả người bán và người mua cùng có lợi.

Bitcoin bảo vệ người mua tương tự như khi dùng tiền mặt. Thực tế thì người mua chỉ cần sự bảo vệ này khi họ muốn đổi hoặc trả hàng, nhưng người bán không đồng ý. Trong những trường hợp như thế này thì người mua có thể sử dụng các dịch vụ ký quỹ trung gian: người mua chuyển BTC cho dịch vụ ký quỹ, người bán giao hàng, người mua kiểm hàng, dịch vụ ký quỹ gửi tiền cho người bán hoặc xử lý tranh chấp. Đây cũng là cách làm truyền thống của các sàn giao dịch như eBay: eBay giữ vai trò ký quỹ và xử lý tranh chấp giữa các khách hàng với nhau.

--

Bitcoin không chỉ là một công cụ thanh toán, mà trên hết nó là một đột phá công nghệ có tiềm năng thay đổi sâu sắc thế giới trong vài năm tới. Những chuyên gia công nghệ kỳ cựu như Paul Graham hay Marc Andreessen cho rằng những cuộc cách mạng như Bitcoin chỉ diễn ra đôi ba lần trong lịch sử.

Lần đầu là giữa những năm 1970 khi người ta phát minh ra máy vi tính cá nhân. Với tầm nhìn "Mỗi nhà sẽ có một máy tính cá nhân chạy phần mềm Microsoft" Bill Gates đã xây dựng lên một đế chế khổng lồ thống trị thế giới công nghệ trong suốt gần hai thập kỷ sau đó.

Lần thứ hai bắt đầu từ lúc Tim Berners-Lee phát minh ra World Wide Web vào năm 1989, để rồi từ đó thế giới có được những Yahoo!, Amazon, Google, Facebook, v.v. Khởi đầu trong một garage ở trái tim của Silicon Valley với hai anh sinh viên còn chưa học xong, mà bây giờ Google đã là công ty lớn thứ hai thế giới. Tất cả nhờ vào việc nhìn thấy tương lai rực rỡ của World Wide Web.

Apple, công ty lớn nhất thế giới, cũng ở Silicon Valley. Họ làm được điều đó vì đã tạo ra được cuộc cách mạng thứ ba: iPhone. Nokia, từ chỗ thống trị thế giới điện thoại, chỉ vì lỡ "chuyến đò" điện thoại thông minh mà đã phải bán luôn công ty chỉ trong vòng vài năm ngắn ngủi.

Từ vài năm nay cả vùng thung lũng điện tử sốt lên vì Bitcoin. Rất nhiều đồng nghiệp của tôi sở hữu Bitcoin và vài người trong số họ đã mở công ty chuyên làm về Bitcoin. Người ta thấy ở Bitcoin một nền tảng mới và ai cũng hiểu rằng những người đầu tiên tận dụng được nền tảng này để sáng tạo ra những sản phẩm và dịch vụ hữu ích sẽ có được cả thế giới. Thanh toán điện tử là ngành công nghiệp khổng lồ có giá trị hàng ngàn tỉ USD và Bitcoin có đủ tiềm năng để làm thay đổi mãi mãi ngành công nghiệp này.

Việt Nam luôn mong muốn trở thành cường quốc về khoa học công nghệ thì không có lý do gì lại sợ hãi và muốn quay lưng lại với phát minh công nghệ cực kỳ quan trọng này. Ngược lại chúng ta cần phải nhìn vào Bitcoin như cách mà các lập trình viên ở Silicon Valley đang làm: sáng tạo như thế nào với công nghệ này để tạo ra sản phẩm và dịch vụ hữu ích. Bitcoin là cơ hội tuyệt vời để ngành công nghệ thông tin vốn rất èo uộc của Việt Nam có được những sản phẩm được cả thế giới sử dụng.

Do đó thay vì cấm Bitcoin, chính phủ nên:

Thứ nhất, nghiên cứu tìm hiểu những vấn đề của Bitcoin và cách giải quyết chúng, để rồi từ đó hợp pháp hóa chính thức việc sở hữu và mua bán BTC. BTC phải được chấp nhận là một hình thức thanh toán hợp pháp ở Việt Nam, tương tự như thẻ tín dụng.

Thứ hai, đầu tư và khuyến khích những công ty, tổ chức, cả tư lẫn công, cung cấp và sáng tạo những sản phẩm và dịch vụ Bitcoin. Chẳng hạn như để BTC trở thành công cụ thanh toán Việt Nam cần phải có một sàn giao dịch Bitcoin.