×

CHALENGE

# PROBLEM

You are given N servers, out of which a vast majority are honeypots. You have to guess the passwords at these servers. You know that the servers mix the passwords with some random salt, and then compare SHA-1 hashes of both the strings.

The score is equal to the sum of the square of the number of bits correctly matched. Honeypot servers do not affect the score at all.

# EXPLANATION

Firstly, you can try to find which servers are honeypot servers.

This can be done by first getting a reference score by using some a set of passwords initially; then

• Change a single password to some other string
• If the score changes, then that server is not honeypot
• Otherwise the server is honeypot

Since we know that the density of honeypot servers is high, we can be smarter and try to find blocks of honeypot servers together. In case we find the score did change for the block of servers we were hoping to be honeypot, we can then try them one by one.

After finding the honeypot servers, we must now try to find the passwords.

The chances of finding the exact password in this problem for any server are extremely narrow. Because of the nature of SHA-1, you cannot even hope to change a string ever so slightly to try and get a better result.

Your best bet is to generate random strings and see which one gets you closer to better and better scores.

One method is to only generate random strings and then try to run the corpus of random strings for each server (of course not for honeypots) while keeping all the other strings constant to try and maximize the score.

This is what the tester's solution does. You have to be careful that you should not exceed the number of attepts you have.

# SETTER'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

2.4k128183169
accept rate: 14%

19.8k350498541

7

@mugurelionut : Can you please explain your solution to this problem .

(16 May '13, 10:55)
4

I don't understand - since a salt is appended to the strings, and we don't know the salt, how can we know the SHA-1 hashes of the strings?

(17 May '13, 05:21) 5★

@neil_812 I have the same question. To quote @gamabunta: " we can ignore any string whose SHA-1 hash matches a lot of bits from this string". But due to the unknown salt this may not give the intended result. Please clarify.

(17 May '13, 09:18)

We just dont know the SHA1 but we try to calculate the number of matched bits after every try using x^2 - y^2 = score1 - score2 where x are the current matched bits. We could run a loop for y from 0 to 160 and a loop for x from y+1 to 160 and check the condition and also check that previously we had matched y bits or not.

(17 May '13, 10:34)
1

supporting @vineetpaliwal ... all top scorers to this problem should explain their logic and expecting reply from @anton_lunyov to this post :)

(17 May '13, 10:50) 4★
1

@balajiganapath indeed. This was my stab at understanding something (if anything at all) from the top submissions. I am going over them again and will update the last section of the editorial.

(17 May '13, 13:05)
showing 5 of 6 show all

 8 At first note that if we change one string in the query and the score does not change, it does not mean that the server is honeypot. It is true only in about 95.5% cases. So often we could miss one or two normal servers. Earlier I do additional tries in this case to identify all normal servers. But in the end I discovered very cool approach that allows to find all normal servers in O(K * log(N/K)) tries, where K is the number of normal servers. We have some initial try {q0[1],...,q0[N]} with score S0. Then we do another random try {q1[1],...,q1[N]} with score S[1,N] and compare their results. If they differ then we have some normal servers. So we make try {q0[1],...,q0[N/2], q1[N/2+1],...,q1[N]}. Let it score be S[1,N/2]. Then score of try {q1[1],...,q1[N/2], q0[N/2+1],...,q0[N]} equals to S[N/2+1, N] = S[1,N] - S[1,N/2] + S0. And we proceed recursively to each of the segments [1, N/2] and [(N+1)/2, N]. So at each moment we are in some segment of servers [L, R] and know the score S[L,R] of try {q0[1],...,q0[L-1], q1[L],...,q1[R], q0[R+1],...,q0[N]}. If S[L,R] = S0 then potentially all servers from L-th and R-th are honeypots and we stop the recursion. Otherwise if R = L + 1 we definitely know that L-th server is normal and we do corresponding processing of scores using squares difference approach described above. Otherwise we do a try {q0[1],...,q0[L-1], q1[L],...,q1[M], q0[M+1],...,q0[N]}. Let it score be S[L, M]. Here M = (L+R)/2. Then as above score of flipped try {q0[1],...,q0[M], q1[M+1],...,q1[R], q0[R+1],...,q0[N]} is S[M+1, R] = S[L, R] - S[L, M] + S0. And we proceed recursively to segments [L, M] and [M+1, R]. If after this recursion we did not identify all normal servers we could apply this step again but for efficiency it is better to delete known normal servers. Actually in my solution I do this in loop while not find all normal servers. Even if we have to identify only one normal server we should spend only O(log H) ties which is not very much. This approach allows me to jump from 9150 to 9250 in average and from 9190 to 9273 at maximum. answered 17 May '13, 13:37 6.7k●62●119●138 accept rate: 12% I also implemented this approach, but while doing this I took at each step a new random string for each server in the interval. And if it was better, remember it, hoping to obtain a better score when T is small. And when the interval(L,R) contains a non-honeypot server, keep trying the intervals (L, (L+R)/2), ((L+R)/2),R) until one also finds one (countering the ~5% case as much as possible). But your approach, using only two strings/server is a big win comparing to mine. Don't forget u don't need to find the lastone, you can just group all resting servers if there is only one to find left. (18 May '13, 18:21) samjay5★
 2 Article on SHA1 collisions here answered 17 May '13, 21:00 3★evandrix 165●1●4●8 accept rate: 0%
 0 SRM Hackathon Hey, SRM Hackathon held in SRM Institute of Science and Technology, (Tamil Nadu) would be a great opportunity for you to horne your technical and development skills. It is a National level Hackathon with great mentors, judges and teams coming up every year. They are going to host their third edition this 26th and 27th September. You can register for it on this link https://srmhacks.hackerearth.com. The registration is completely free and there are many exciting prizes worth INR 3 lakhs and innumerable learning and connecting experiences to be earned by every participant It's surely worth giving a try :) answered 18 Aug '18, 22:16 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×947
×847
×128
×72
×18

question asked: 16 May '13, 05:56

question was seen: 4,126 times

last updated: 12 Jun '14, 20:55