UNIX crypt function is a hash function
Budget: $10 – $30 USD
The UNIX crypt function is a hash function that only looks at the first eight bytes of
the input message. For example, crypt(helloworld) returns the same value as crypt(hellowor).
Some web sites use the following authentication method to authenticate users: (1) the user types in a user-id and a password P into his web browser, (2) the site, upon verification of the password P , computes T =crypt(user-id||K), where || denotes string concatenation, and K is a l-byte site secret key l ≤ 8, (3) the site sends a cookie back to the user containing T , (4) the user can use T to authenticate himself to the site in future connections.
Show that by choosing clever user-id’s (of varying length) an attacker can expose the site’s secret key K in time approximately 128l. More concretely, the user creates an account, logs in and receives the corresponding T ; he then creates another account (with a different user-id, logs in and receives another T . By repeating this sufficient times, the user recovers K completely. We are assuming there are 128 possible values for each character in a string.
Hint: Try to recover one character of K for each account created. The attack is described in the pa- per “Dos and Don’ts of Client Authentication on the Web” in USENIX Security Symposium, 2001. Reading the paper is allowed.
the input message. For example, crypt(helloworld) returns the same value as crypt(hellowor).
Some web sites use the following authentication method to authenticate users: (1) the user types in a user-id and a password P into his web browser, (2) the site, upon verification of the password P , computes T =crypt(user-id||K), where || denotes string concatenation, and K is a l-byte site secret key l ≤ 8, (3) the site sends a cookie back to the user containing T , (4) the user can use T to authenticate himself to the site in future connections.
Show that by choosing clever user-id’s (of varying length) an attacker can expose the site’s secret key K in time approximately 128l. More concretely, the user creates an account, logs in and receives the corresponding T ; he then creates another account (with a different user-id, logs in and receives another T . By repeating this sufficient times, the user recovers K completely. We are assuming there are 128 possible values for each character in a string.
Hint: Try to recover one character of K for each account created. The attack is described in the pa- per “Dos and Don’ts of Client Authentication on the Web” in USENIX Security Symposium, 2001. Reading the paper is allowed.