mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)
-   -   password bug puzzle (https://www.mersenneforum.org/showthread.php?t=9635)

jasong 2007-11-23 19:42

password bug puzzle
 
I have no idea how to even begin to solve this, I just want to see what strategies people use. :)

It is imperative that you break into a facility that's protected by keycards. You need access to all the sections.(I'm not going to say how many sections there are, we'll make that an open variable to study) You have one computer and a card attached to it, so you can come up with any passcode combination. Each time you attempt a combination that's wrong you're locked out for one minute. The passcode is 64 bits, meaning 2^64 combinations, but there's a bug in the software. Each time you attempt a guess, you find out if the number of bits that are correct is odd or even(you impersonate a specific employee with the card, so the passcode is the same for individual sections). For each section, you have to guess a new 64-bit passcode.

Also, there is a master passcode, but it's 512 bits. After we figure out the approximate time for the 64-bit passcode, we want to know how many sections in the facility there would have to be for it to be a good idea to go straight for the 512-bit passcode.

For the sake of the puzzle, the guards are all looking at porn on the Internet and will never notice you're there. ;)

axn 2007-11-23 20:18

[QUOTE=jasong;119044]The passcode is 64 bits, meaning 2^64 combinations, but there's a bug in the software. Each time you attempt a guess, you find out if the number of bits that are correct is odd or even[/QUOTE]

[SPOILER]The bug gives exactly one bit of information -- namely, the parity of the passcode. Additional tries will not give any additional information. So the only way you'll ever crack a passcode is if you get the whole code right at one go and the door opens. So your best strategy is to join the guards and watch some porn ;)[/SPOILER]

jasong 2007-11-23 20:23

For those of you who read axn's answer, I don't believe he's correct in saying it's impossible to solve. I have a germ of an answer, but I want to see what other say.

Citrix 2007-11-23 23:25

[QUOTE=jasong;119044]
The passcode is 64 bits, meaning 2^64 combinations, but there's a bug in the software. Each time you attempt a guess, you find out if the number of bits that are correct is odd or even(you impersonate a specific employee with the card, so the passcode is the same for individual sections).

[/QUOTE]


[spoiler] Due to this bug it will take you 64 steps to crack the 64 bit code for each section. I don't understand the 512 bit thing.

[/spoiler]

jasong 2007-11-24 00:50

[QUOTE=Citrix;119076][spoiler] Due to this bug it will take you 64 steps to crack the 64 bit code for each section. I don't understand the 512 bit thing.

[/spoiler][/QUOTE]
Sorry, I meant sections of the lab you're breaking into, not sections of the passcode. I wanted to have a good backstory. :)

Fusion_power 2007-11-24 03:59

31 minutes to crack each of the 64 bit codes. There might be a way to optimize it still further, but 31 was the best I could get.

Following this through, you could crack the 512 bit code in 255 minutes. That means the master code should be attempted if there are 8 or more sections to the area.

And no I won't post how I came up with 31 tries. But it is really simple.

DarJones

Wacky 2007-11-24 10:37

[QUOTE=Fusion_power;119090]31 minutes to crack each of the 64 bit codes.
And no I won't post how I came up with 31 tries. But it is really simple.[/QUOTE]

Actually, in just over 31 minutes, you can get 32 tries.

But I agree with axn1. It isn't that easy.

After the first test reveals 1 bit of information, each of the rest can add only about 2^(-63) additional bits to the information.

Now, if the test were to reveal something about the number of 1's without caring about any of the 0's, that would be a different situation.

However, as the problem is stated, after the first test, I can completely predict the outcome of any other test, if it fails.


All times are UTC. The time now is 19:32.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.