password bug puzzle

[jasong]

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]

Originally Posted by jasong

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

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 ;)

[jasong]

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]

Originally Posted by jasong

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).

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.

[jasong]

Originally Posted by Citrix

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.

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]

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]

Originally Posted by Fusion_power

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.

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.