Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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!

share|improve this question
1  
You need to reverse engineer the algorithm first. You need to extract the public key. –  David Schwartz May 4 '12 at 6:52
    
@David: you mean, disassembling the bios? there is no pure mathematical approach to solve this kind of puzzle? –  Paulo Scardine May 4 '12 at 13:52
1  
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 May 4 '12 at 19:19
    
@PauloScardine: There is, you just don't know what the puzzle is yet because you haven't extracted the public key. That would be the first step. –  David Schwartz May 4 '12 at 20:14
    
With a 64 bit modulus you can simply factor via trial division at cost $2^{32}$. –  CodesInChaos 15 hours ago

2 Answers 2

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.

share|improve this answer

I think that number OTP 4x4 XXX-XXXX-XXXX-XXXX is in Base64 Alphabet, so convert this to Decimal and you have a big Integer. Factorize, and you'll obtain a couple of primes numbers, with which you can to generate a public and private key. With those keys, using the Euler law (RSA Encryption base) you can decipher the password.

share|improve this answer
    
I doubt its Base64, since that would require two non-alphanumeric characters ($26*2+10=62$), and would be case sensitive. Seems much more likely to be encoded within the 36 letters+numbers in some way. Also, not convinced your approach will work: what do you think the challenge encodes? It sounds like you think the challenge is the RSA modulus, in which case how would you get the public/private key from it? Just knowing $\varphi(n)$ doesn't tell you anything about $d,e$. –  figlesquidge Dec 12 '13 at 10:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.