Hex puzzle (2)

Let's continue with the puzzle introduced in the last post (here).

The next step is to stitch the lines together to form the complete text. If they contained random bytes, that would be relatively easy. There are 65536 possible two-byte combinations. We have a total of 340 * 25 = 8500 two-byte (4 hex character) combinations in our data, so the expected number of times any combination should appear in random data is much less than 1.

However, the data is not random, instead, it is highly skewed. Simple modifications to count.py (from last time) show a total of only 370 two-byte combinations in the data (i.e. 65166 of all possible values are not observed), and the top 20 have counts ranging from 464 down to 72.

464 4341 CA 331 4943 IC 309 4167 Ag 281 4c43 LC 234 734c sL 174 4173 As 154 4377 Cw 140 7773 ws 139 7349 sI 139 674d gM 139 674c gL 137 4c44 LD 126 674e gN 104 6749 gI 103 7767 wg 95 4e69 Ni 89 5973 Ys 78 4944 ID 76 4947 IG 72 4e6a Nj

In the table above, the first column is the count, the second and third are the hex and ASCII representations.

That compares with a maximum count of 3-4 for random data, and an observed total of 8000 different values on an average run with random data.

This suggests that we should undertake some data exploration to see whether the repetitive character of the data will cause difficulties for the assembly.

The core operation is to take an individual entry at index i in the data (the query), and depending on a parameter (tlen) for the number of characters to choose at the very end of the query, make a substring sequence t, the target to search for. Then, we go through all the other entries looking for a match containing t, and when one is found we save the index of the query and the match as well as the position k where the target t begins in the match string.

The quality of these matches can be assessed in various ways. We expect that the sequence of each match string upstream of the target should be exactly the same as the query. We calculate the offset o where the beginning of the match string should be found in the query. Since this depends on tlen (o = len(L[i]) - k - n) we calculate it for each hit and save it with the other parameters. The offset is also useful for printing the actual alignments in show.

A second quality test is to examine the match strings downstream of the target. In the region of overlap, we expect they should be identical as well. A failure of either test would suggest that the data is causing trouble for our simple search algorithm.

---

As mentioned last time, the observed hex digits comprise all (and only) those which encode ASCII characters 0..1A..Za..z. Rather than print out strings of 100 characters, it will simplify the output to convert the data to ASCII first. We're assuming that this is what we need to do with the data, but I peeked at the answer on reddit, so it's safe to go ahead.

python convert.py > data.mod.txt

import binascii from utils import load_data L = load_data('reddit.txt') for line in L: print binascii.unhexlify(line)

Note the extremely repetitive nature of the data by comparing some adjacent output lines:

A1NiAsNiAsMyAsMSA0NiwsICAyJyxmICcwLCwgIDc2KSw7ICAx A1NywsICAyNSwsICA0NiwsICAyJyxmICcwLCwgIDc2KSw7ICAx AgLDUgLDcgLDMgLDAgLDAgLDcgLDIgLDIgLDYgLDYgLDEgNTQs AgLDUgLDcgLDMgLDAgLDAgLDcgLDYgLDIgLDYgLDYgLDEgNTQs xpIG42dCwgIG00YSxpIG42KCwpICAzeywgICAyICwgICA2ICxp xpIG43dCwgIGE3WyxdICA3PSwgIHswNCwsICA2NCwsICAxNiws

However, for a well-chosen query (one with a rare two-byte combination as the target) and a long enough target length, it's easy to find matches that appear correct. In the output below, we examine the string found at index 0 in the data as the query. The analysis finds 25 matches, data strings where the terminal 4 characters appear somewhere in the match, and all of those matches are perfect ones whether looking upstream and comparing against the query, or looking downstream in each one (beyond the target) and comparing with each other, as shown in the second half of the output.

We'll exercise these routines a bit more next time. I want to see how big to make the target size, and also whether we should exclude some strings from the preliminary analysis. But overall, it looks like we might be OK.

> python search.py i= 0 : 25 matches found 0NiwsICAyJyxmICcwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc GExc NiwsICAyJyxmICcwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc iwsICAyJyxmICcwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc CAyJyxmICcwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc AyJyxmICcwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc xmICcwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc mICcwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc CcwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc cwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc wLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc LCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc CwgIDc2KSw7ICAxJCxiICA2PSwgIGExc wgIDc2KSw7ICAxJCxiICA2PSwgIGExc gIDc2KSw7ICAxJCxiICA2PSwgIGExc CAxJCxiICA2PSwgIGExc AxJCxiICA2PSwgIGExc xJCxiICA2PSwgIGExc JCxiICA2PSwgIGExc CxiICA2PSwgIGExc xiICA2PSwgIGExc A2PSwgIGExc 2PSwgIGExc SwgIGExc gIGExc IGExc GExc no mismatches upstream GExc j jR jRyLGE jRyLGEg jRyLGEgeTYo jRyLGEgeTYoL jRyLGEgeTYoLDc jRyLGEgeTYoLDcg jRyLGEgeTYoLDcgL jRyLGEgeTYoLDcgLD jRyLGEgeTYoLDcgLDQ jRyLGEgeTYoLDcgLDQg jRyLGEgeTYoLDcgLDQgL jRyLGEgeTYoLDcgLDQgLDkgLDIgLDY jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYg jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgL jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLD jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLDA jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLDAg jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLDAgLDUg jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLDAgLDUgL jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLDAgLDUgLDc jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLDAgLDUgLDcgL jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLDAgLDUgLDcgLD jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLDAgLDUgLDcgLDM no mismatches downstream

search.py

from utils import load_data # tlen is minimum overlap # functions deal with one string at a time # do not assume upstream matches # e is search string, f is potential match def one_search(i,L,tlen): # search result has associated tlen oL = list() e = L[i] t = e[-tlen:] for j,f in enumerate(L): if i == j or not t in f: continue # offset is pos in e where f should start # not guaranteed to match except over t offset = len(e) - f.index(t) - tlen oL.append((j,offset)) oL.sort(key=lambda item:item[1]) return oL # mmL is a list of mismatched strings # ummL contains upstream mismatches def test_upstream(i,L,oL,ummL): e = L[i] for j,o in oL: f = L[j] if not f.startswith(e[o:]): if i < j: ummL.append((i,j)) else: ummL.append((j,i)) def trim_downstream(oL,L,tlen): pL = list() for j,o in oL: f = L[j] k = len(f) - o pL.append((j,f[k:])) return pL def test_downstream(pL,dmmL): mismatches = 0 for i,s1 in pL: for j, s2 in pL: if s1 == s2 or len(s1) < len(s2): continue if not s1.startswith(s2): if i < j: dmmL.append((i,j)) else: dmmL.append((j,i)) if __name__ == '__main__': L = load_data('data.mod.txt') tlen = 4 i = 0 e = L[i] oL = one_search(i,L,tlen) print 'i=', i, ':', len(oL), 'matches found' print e print ' ' * (len(e)-tlen) + e[-tlen:] print for j,o in oL: k = len(e) - o print ' '*o + L[j][:k] ummL = list() test_upstream(i,L,oL,ummL) if ummL: print len(ummL), 'mismatches' else: print 'no mismatches upstream\n' dmmL = list() print e[-tlen:] pL = trim_downstream(oL,L,tlen) for item in pL: print ' '*tlen + item[1] test_downstream(pL,dmmL) if dmmL: print len(dmmL), 'mismatches' else: print 'no mismatches downstream'

Hex puzzle (1)

Last Saturday, an interesting puzzle was posted on reddit/r/programming. I'm having trouble finding the original post, but the actual puzzle page is here, and the (complete) comments to the post are here.

As you can see from the screenshot or the link

the puzzle is a message consisting of 1936 hex digits, and upon further manipulation it promises to yield the answer. You can actually follow the link to see the answer if you're impatient. I wasn't able to compete (I had a party to cook for, and could not have gone as fast as these guys anyway), but I'd still like to understand how they got there.

Apparently, we need to assemble a number of overlapping 100 digit pieces of a 1936 digit message and then figure out what it means. The pieces were served up to different visitors to the site and collected as comments on reddit. The first objective is to recover the observed data. I believe reddit must have an API for this, but I don't know it. What I did was to save the source for the page with all 410 comments (in the file comments.txt) and then run scrape.py below.

I count 251 strings of 100 characters, all in "0..9a..f".

According to the instructions, the first and last strings are marked, and these were recovered and posted on reddit:

497a78705032357759326873634855675a43526c595341675044317a494852685a484a70636d39684c6e6c6f4b4434354369 //first 100
4270494630674f3349675a5831304948566c636d4e75614342764d4341374a79426c494363674f7941674944393950676f3d //last 100

[UPDATE: There is a link to the complete (known) data from reddit to github here. I count a total of 340 strings, substantially more than what I've been working with in early attempts. This should help with the assembly problem. ]

The data clearly has substantial structure, as indicated by the screenshot from a "find" search for the digit "4" in TextEdit.

Since only hexadecimal digits are present it suggests that this might actually be hexadecimal. It's interesting that not all digits are equally represented. In particular, only those bytes (two hex digits) which encode ASCII "a..zA..Z0..9" are present (although the distribution is decidedly odd). So it seems pretty likely that we just need to decode the hex to ASCII and then figure out what it means.

However, there is an assembly problem that comes first.

Output from count.py (listing at the end):

> python count.py 54 30 48 0 0 40 31 49 1 1 256 32 50 2 2 71 33 51 3 3 58 34 52 4 4 82 35 53 5 5 64 37 55 7 7 39 38 56 8 8 63 39 57 9 9 1070 41 65 A A 133 42 66 B B 1102 43 67 C C 414 44 68 D D 111 45 69 E E 38 46 70 F F 169 47 71 G G 101 48 72 H H 812 49 73 I I 151 4a 74 J J 132 4b 75 K K 667 4c 76 L L 399 4d 77 M M 532 4e 78 N N 83 4f 79 O O 82 50 80 P P 67 51 81 Q Q 65 52 82 R R 286 53 83 S S 58 54 84 T T 51 55 85 U U 12 56 86 V V 56 57 87 W W 31 58 88 X X 315 59 89 Y Y 92 5a 90 Z Z 16 61 97 a a 13 62 98 b b 278 63 99 c c 61 64 100 d d 58 65 101 e e 8 66 102 f f 938 67 103 g g 57 68 104 h h 247 69 105 i i 201 6a 106 j j 116 6b 107 k k 62 6c 108 l l 64 6d 109 m m 97 6e 110 n n 61 6f 111 o o 209 70 112 p p 896 73 115 s s 25 74 116 t t 23 75 117 u u 15 76 118 v v 532 77 119 w w 211 78 120 x x 414 79 121 y y 192 7a 122 z z

scrape.py

# python scrape.py > data.txt fn = 'comments.txt' FH = open(fn) data = FH.read() FH.close() L = list() i = 0 while True: j = data.find('>',i) j += 1 i=j k = j + 100 if k > len(data): break if not data[k] == '<': continue w = data[j:k] if ' ' in w or '>' in w or '<' in w: continue for c in w: assert c in '0123456789abcdef' L.append(w) if i == 0: break L = list(set(L)) L.sort() for w in L: print w

count.py

import binascii from collections import Counter def load_data(): fn = 'data.txt' FH = open(fn,'r') data = FH.read().strip() FH.close() L = data.split('\n') return L L = load_data() n = 2 cL = list() for line in L: for i in range(0,len(line)-n+1,2): cL.append(line[i:i+n]) C = Counter(cL) for h,n in sorted(C.most_common()): i = int(h, base=16) print '%4d %s %4d %s %s' %\ (n, h, i, chr(i), binascii.unhexlify(h))