BREW’r’Y (Category: Crypto) Author(s): dwuid
Finally, the robots managed to sneak into one of our breweries. I guess I won’t have to explain how bad that really is. That darn non-physical ones even shutdown our login system. Shiny thing, advanced technology, all based on fingerprints. Been secure as hell. If only it was running. Well, basically, we’re screwed.
But wait, there’s hope. Seems like they didn’t shutdown our old login system. Backward compatibility’s a bitch, eh? Unfortunately, we got like _zero_ knowledge about the protocol. I mean come on, the last time we used that thingy was like decades ago. If we are lucky, the old authentication method is buggy.
So, I heard you’re kinda smart? Have a look at it. We desperately need to get drunk^W supply. You’ll find the old system at ctf.fluxfingers.net:1335. Good luck.Hint: Data is – and is expected to be – compressed using zlib.
Hint: The challenge text gives hints about the protocol involved.
Summary: Hamilton path bugged check
Let’s connect and see what’s there:
$ nc -v ctf.fluxfingers.net 1335 ctf.fluxfingers.net [149.13.33.74] 1335 (?) open ________________________________________________________________________________ BREW'r'Y graphICAL LOGIN PANEL - (Stage 1) [ "Beer you, beer me, beer us together." ] ________________________________________________________________________________ Session ticket #267: eJw1l4dxxDAMBFtRCaKY+2/Mt4v3jH1HUIyI/Pa07z7taf0D32Z7gu0Ev07zS+O5N9DeHjy2xIY8+d7b05+zAzP/rV1wrGAWCdi6z8hyB8xewfEGx6Rpb1vBebJG6xt8AfGw8pmBuZ/1rBNgUGZ8gU2rp/+5nS/ZcGfmDHaa4yJnv+2pN+vtJ2fJPd9Iz2k0M+F4jJzBZi5/PXMuNAPZLDCABdzA4T5P7+DaYL4F27Crtc8vaPVZ3CcHL+GWMCRGN24fzCUy63IRp6DrVmRfG0f6+H9m1uluHV2Lrtm9WojjdG7Id871YPBcApU82559Qa6Sv2nXpVUOMbU9FMtKfovBwQPeLM8+L7RLeKc07OPIUewHxmfafvYHDtvRKTjB+jrtibXjG/foIS+4O4gHhr4JottbGrxYFuF7FS6IUu//qC92f71jKIshNIW4VzD7BmOh4MrnpvM3XC7INIy1FaZCrCBF0mjBHBW0jemgad9VuJPAiF8F9zLSml3rFfNN+wRZCmteadgXO4HTrpwzW8dNgrE7Kili7DQ+p47zYZJRdKF9FIYCpg3drIYTS/GmT9vYdaWmxN7ba2iR4BTjDB8ubHCp62t+kQZ0FM5rFxoqm3SDR/f8oAxQqL5WA7RLDBGMOxNFcTFoSCSgD4fGv/uBhl1Hlz/27GGskrG6iSjE2MRJtyuGCK0PZXKkoQVD0VNX6+DxA54ycVuiJKEYih7AIZo2WGrh7b1iQuoQKxI0C03HyXtpPjQKGzgXByS0QlvkWkdbhDjRIVx75arQVuBCpis+DD+cBUaR5EKdK/4RvJ+BSI5uqgDKlFC2H1UHSLUD3Laz/Pj0i9BUZsnuYmqQ9uQAsSb4GecsO11j1lYTAyHEKENNmUGXSVY/XuL24lHaMEmQUd6vyPySJIbA+uWDIc5yq+B470ThWiCKhsgPL4kimGxDV0VN9sylGJwL2962cbYQFenTdWc3HUHJsBBLqYCpAuIMSQsktPIMDD4rmOfUU6Eoa6qJ4BYpY9F+dB5MlM1Vmy/MiPBZDomv0BF35cxh1ov7kvtG1RWmHnySgvHa2vqoo/GdgYaI01CUjUBfU88hyiyu0IsWV4zSg9frslByVxIXeMBtD54ais7W0MzQu4q21IrYb+rGUsMAVPtlsoBYatUhqtxvbygNxpLkINz11IoXdwN3VV27cJRljUAgE79GQOgaaCRNhGFBSyRC2Qp69dMfRVcI2X7rGNQoUg2kdI02Rw8PtqcBvet9AzF54q67DL/rgRM6Iv4hHenTGqgylGyE8Bki6G7XvaWJDRKAwVQyCn0S1XmtyyFePnVVXgjUzMZxT9n5VIBDKbSh6wUZYBI89VY7ldkgnhoLpR6LySk35alA+tkaGqLgHk5EjSaLXRVzqnbfV5+Tuo+LH5Eo65l6KyndOuj9jGiI6b2md5f2ObV80DCvEvqth86tLH6npocSGby8YjjoJ0UvEBN2jaxULX31lNJtsKpkAKDqe/VIaUsWgFdDyTxseH2T0uFRL2Rf4e/3+17vbd9hlEy4bVduFrLxm18RJZNS33I0ebSfXI7rm9In4m9Or7zgs/K9v3mVHmQfM2+dv1VVLj7FvjN+55ZXvX77P5fvkfe8i3L9XPBF2av0+ORkDaqA3LW05/h+68Cj/XjrAuoTdnwZW/7l9Jq3ap+v6i4xg9sVr9It+vfx8fttxPdeiV9d95/OfWzXDx3XGj8bWOR+5x2/eYwZ+w+O8mcm Commit round authorization: |
We see another hint – “graph”. So let’s decode base64 and zlib:
In [3]: zlib.decompress( s.decode("base64") ) Out[3]: '1 129 1 132 1 101 1 135 1 118 1 23 1 121 2 99 2 103 2 8 2 108 2 113 2 51 2 31 3 87 3 5 3 119 3 146 3 23 3 26 3 29 4 128 4 101 4 140 4 45 4 18 4 116 4 58 5 137 5 10 5 110 5 83 5 85 5 57 6 68 6 137 6 42 6 77 6 36 6 93 6 126 7 115 7 36 7 ... |
We see a bunch of numbers. Remember it should be a graph: we can pair the numbers so it will be a list of edges. Also we see that edges connect smaller numbers to bigger – so most probably it’s an undirected graph.
Remember the hint about zero knowledge protocol (google and find this). Seems we need to prove we know a Hamilton path (Hamilton cycle here actually) for a given graph. (Hamilton path is a path that visits all the points in graph bu each point only once) We need to send some graph to the server and the server will ask either a permutation (which must map original graph to the one we sent) or a Hamilton path on that graph.
We can send some simple graph in which we know a Hamilton path and if the server asks for it we will know it. Or we can make a random permutation of the original graph. The chance is 50% in both cases.
Another problem is to guess format of the answers. Permutation is sent in form [old_point1, new_point1, old_point2, new_point2, ...]. Hamilton path is send as just list of points. Both lists are encoded in the same manner (numbers separated by spaces, compressed and base64’d).
Actually, there are 3 stages in the challenge:
- Stage 1: 1 request with 150 points graph. (We can easily win by chance)
- Stage 2: 20 requests with 50 points graph. (Random path in such graph is rather to be a Hamiltonian, so we indeed can prove it)
- Stage 3: 20 requests with 150 points graph. (Oh.)
3rd stage introduces masked authorization. Guess that mask is simple xor. We need to mask our graph with random numbers xor, and after sending a permutation or a path we must show our mask. Well, I think we can use that and generate different masks for different request types.
So I guess it was intended to move through the stages one-by-one and apply different methods for each stage.
But aactually there’s a bug in check so we can solve all the 3 stages using that bug and avoid implementing different techniques for each stage.
The bug is rather easy to find – if you send an extended graph (with additional edges) – it is accepted as a valid permutation of the original one. So we can easily send both a permutation and a Hamiltonian path – just add any edges you want.
Here’s the code:
import random, zlib from sock import * def decode(s): s = zlib.decompress( s.decode("base64") ) return map(int, s.split()) def encode(lst): s = zlib.compress(" ".join(map(str, lst)), 9).encode("base64") # fuck python! I've wasted lots of time on this s = s.replace("\n", "") return s def encode_perm(perm): lst = [] for i, v in enumerate(perm): lst.append(i + 1) lst.append(v) return encode(lst) def do_graph(graph): LEN = max(graph) perm = range(1, LEN + 1) random.shuffle(perm) graph = [perm[i-1] for i in graph] edges = zip(graph[::2], graph[1::2]) ham_path = range(1, LEN + 1) random.shuffle(ham_path) for edge in zip(ham_path, ham_path[1:] + ham_path[:1]): if edge not in edges and edge[::-1] not in edges: edges.append(edge) newgraph = [p for edge in edges for p in edge] return newgraph, perm, ham_path def read_stage_head(): f.read_until("ticket #") f.read_until("\n") s = f.read_until("\n") return decode(s) def do_step(graph, stage): f.read_until("authorization:\n") newgraph, perm, ham_path = do_graph(graph) if stage == 3: newgraph = [0x41 ^ c for c in newgraph] f.send(encode(newgraph) + "\n") req = f.read_until(":\n") print "STAGE %d request:" % stage, req.strip() if "type A" in req: f.send(encode_perm(perm) + "\n") else: f.send(encode(ham_path) + "\n") if stage == 3: f.read_until("mask:\n") f.send(encode([0x41 for c in newgraph]) + "\n") f = Sock("149.13.33.74", 1335) graph = read_stage_head() do_step(graph, stage=1) graph = read_stage_head() for i in range(20): do_step(graph, stage=2) graph = read_stage_head() for i in range(20): do_step(graph, stage=3) print f.read_all() |
$ py wup.py STAGE 1 request: Requesting round authorization ticket, type A: STAGE 2 request: Requesting round authorization ticket, type B: ...(20 requests) STAGE 2 request: Requesting round authorization ticket, type A: STAGE 3 request: Requesting round authorization ticket, type A: ...(20 requests) STAGE 3 request: Requesting round authorization ticket, type A: Welcome to our main interface. Your BREW'r'Y identification is: iN.D3sPER4T3.n3Ed.0F.PHRiTZk3Wli. (Closing connection.) |
The flag: iN.D3sPER4T3.n3Ed.0F.PHRiTZk3Wli
1 comment
give me your contact pls