mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2007-11-23, 19:42   #1
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5×701 Posts
Default 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. ;)
jasong is offline   Reply With Quote
Old 2007-11-23, 20:18   #2
axn
 
axn's Avatar
 
Jun 2003

7×11×61 Posts
Default

Quote:
Originally Posted by jasong View Post
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 ;)
axn is offline   Reply With Quote
Old 2007-11-23, 20:23   #3
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

DB116 Posts
Default

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.
jasong is offline   Reply With Quote
Old 2007-11-23, 23:25   #4
Citrix
 
Citrix's Avatar
 
Jun 2003

157310 Posts
Default

Quote:
Originally Posted by jasong View Post
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.


Last fiddled with by Citrix on 2007-11-23 at 23:28
Citrix is offline   Reply With Quote
Old 2007-11-24, 00:50   #5
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5×701 Posts
Default

Quote:
Originally Posted by Citrix View Post
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. :)
jasong is offline   Reply With Quote
Old 2007-11-24, 03:59   #6
Fusion_power
 
Fusion_power's Avatar
 
Aug 2003
Snicker, AL

7·137 Posts
Default

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
Fusion_power is offline   Reply With Quote
Old 2007-11-24, 10:37   #7
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32×112 Posts
Default

Quote:
Originally Posted by Fusion_power View Post
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.

Last fiddled with by Wacky on 2007-11-24 at 10:50
Wacky is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ROLP password Stargate38 No Prime Left Behind 7 2011-09-24 20:25
username and password in url? stars10250 PrimeNet 30 2009-07-02 14:13
Forgot my password Unregistered Information & Answers 1 2007-05-30 21:52
user ID and password Prodigious Software 2 2003-11-20 03:59
how do I changed password ? sankotm Software 1 2003-09-05 23:56

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

Thu Sep 24 19:32:39 UTC 2020 up 14 days, 16:43, 0 users, load averages: 2.09, 1.73, 1.76

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.