OTP from Sony BIOS password recover From Dogbert's blog:


  Sony has a line of laptops ("Vaio") which compete mainly in the high value market segments. They implemented a master password bypass which is rather sane in comparison to the rest of the bunch:
  
  
  The randomly generated master password is only stored in RAM, e.g. it's lost after the next reboot ("one time password").
  RSA is used for encrypting the password which is then converted to a human-readable form (4x4 characters/8 bytes/64 bits).
  Their customer support apparently allows for one free password generation per device which is pretty decent by the industry standard.
  


Dogbert claims he was able to factor the password used to encrypt the OTP key because Sony used a key lenght of 64bits. And did this using an unoptimized python implementation of a general number sieve in less than a minute.

I was not aware that such small key length was even possible for RSA (I think pycrypto will not allow anything below 1024).

With a key (D63K-XFVF-TK7H-RJKX) and a password (43878945) is it really that easy to figure out the scheme used? How should I approach the problem?

[UPDATE]


  First of all, RSA works for any size modulus. 10 bits, 32 bits, 64 bits, 1 million bits. I'm having a hard time seeing exactly what the question is. You are given the key (D63K-XFVF-TK7H-RJKX). Is that key the RSA key? That key then encrypts the password (43878945)? Or is that key the result of encrypting the password with RSA? – mikeazo 2 days ago


@mikeazo: it is a challenge-response theft protection. Type the wrong password 3 times and you will be presented the 16 character challenge. You call Sony customer support, fax them a proof of purchase and based on the challenge they will give you a password. You can't brute-force it because it changes every time.

@Schwartz: of course, Dogbert disassembled the Sony Vaio BIOS and got the public key! Calculating the private key was the easy step... I was not thinking like a hardware hacker, thanks!
If they pad the key with some fixed value and apply RSA directly to it then it is just a textbook RSA scheme which is vulnerable to meet-in-middle attack: it runs roughly in time $2^{40}$ and requires $2^{32}$ space.