{"id":90,"date":"2020-10-12T17:57:05","date_gmt":"2020-10-12T22:57:05","guid":{"rendered":"https:\/\/theshrouded.com\/wp\/?p=90"},"modified":"2024-12-19T15:35:51","modified_gmt":"2024-12-19T20:35:51","slug":"damctf-2020-semihonest","status":"publish","type":"post","link":"https:\/\/theshrouded.com\/wp\/?p=90","title":{"rendered":"DamCTF 2020 “semihonest”"},"content":{"rendered":"\n

OT is secure
I hope you will not break it
Don’t be malicious<\/p><\/blockquote>\n\n\n\n

This challenge provides you with incomplete client code for an Oblivious Transfer (OT) protocol. In Oblivious Transfer there is a “sender” and a “receiver”, the sender won’t know what data was sent to the receiver, and the receiver will only learn the information it requested. See this Wikipedia article<\/a> for more information.<\/p>\n\n\n\n

The challenge server will tell you that the flag has been split into 2 shares and that you must XOR them together to get the flag. However, getting both shares in a single session is impossible if we play “honestly”. <\/p>\n\n\n\n

The challenge name is “semihonest” which suggests that the OT protocol implemented has an assumption that at least one party is acting “honestly”. Well, we can just be a little less than honest and get the flag. In particular, the client code provided only calculates 1 key that it knows the secret to and another that is just random. In oblivious transfer the sender doesn’t know which share the client requested so it looks like the server would have to send back 2 valid shares in this case.<\/p>\n\n\n\n

I first tried sending the same key twice, but the server checks for that. Drats, its never that easy… So we need to just call our public key and shared key generator again, and save a second key. I stopped caring about the “choice bit” because it doesn’t matter in the end if we can decrypt both shares the server sends back. So all that remains is filling in the missing client code and then computing the XOR of the 2 shares we decrypt.<\/p>\n\n\n

\ndef gen_key(g, p, B):\n    """\n    Choose random a \\in [1, p-2]\n    find A: g ^ a mod p\n    find KA: B ^ a mod p\n    output: A, KA\n    """\n    a = get_rand(p)\n    A = pow(g, a, p)\n    KA = pow(B, a, p)\n    return A, KA\ndef otp_decrypt(key, p, ctext):\n    """\n    output: ctext * key^-1 mod p\n    Hint: You will need to compute modular inverse\n    """\n    return (ctext * get_inv_mul(key, p)) % p\n\n# Get modular multiplicative inverse\ndef get_inv_mul(e, n):\n    gcd, x, _ = xgcd(e, n)\n    if gcd != 1:\n        raise Exception('Modular inverse does not exist')\n\n    return x % n\n\n\n# Extended Euclidean Algorithm\n# Ref: https:\/\/anh.cs.luc.edu\/331\/notes\/xgcd.pdf\ndef xgcd(a, b):\n    x0, x1 = 1, 0\n    y0, y1 = 0, 1\n    while b:\n        q = a \/\/ b\n        x1, x0 = x0 - q*x1, x1\n        y1, y0 = y0 - q*y1, y1\n        a, b = b, a % b\n\n    return a, x0, y0\n<\/pre><\/div>\n\n\n
And for the actual “semihonest” part of the challenge this was my run_client<\/code> function (comments intact to line up):<\/p>\n\n\n
\n        # Generate our D-H public key and shared key\n        pkey1, ka_key1 = gen_key(generator, modulus, server_pkey)\n        pkey2, ka_key2 = gen_key(generator, modulus, server_pkey)\n\n        \n        # The server will encrypt each plaintext with our keys\n        keys[0] = pkey1\n        shared_key[0] = ka_key1\n        keys[1] = pkey2 #get_rand(modulus)\n        shared_key[1] = ka_key2\n        formatted_keys = ','.join(str(key) for key in keys).encode()\n\n        # Send keys to server\n        s.send(formatted_keys)\n\n        # Receive both ciphertexts from server encrypted with respective keys\n        ctexts = receive_ints(s)\n\n    # Decrypt the one ciphertext we can decrypt (as determined earlier by choice_bit)\n    ptext = otp_decrypt(shared_key[0], modulus, ctexts[0])\n    ptext2 = otp_decrypt(shared_key[1], modulus, ctexts[1])\n\n    print("Decrypted text:")\n    pbytes = to_bytes(ptext)\n    print(pbytes)\n    print("Decrypted text:")\n    pbytes2 = to_bytes(ptext2)\n    print(pbytes2)\n\n    print("".join([chr(x^y) for x,y in zip(pbytes, pbytes2)]))\n\n    return 0\n<\/pre><\/div>","protected":false},"excerpt":{"rendered":"
OT is secureI hope you will not break itDon’t be malicious This challenge provides you with incomplete client code for an Oblivious Transfer (OT) protocol. In Oblivious Transfer there is a “sender” and a “receiver”, the sender won’t know what data was sent to the receiver, and the receiver will only learn the information it […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[22],"tags":[11,4,10,13,12,9],"class_list":["post-90","post","type-post","status-publish","format-standard","hentry","category-write-ups","tag-crypto","tag-ctf","tag-damctf","tag-oblivious-transfer","tag-ot","tag-write-up"],"_links":{"self":[{"href":"https:\/\/theshrouded.com\/wp\/index.php?rest_route=\/wp\/v2\/posts\/90","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/theshrouded.com\/wp\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/theshrouded.com\/wp\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/theshrouded.com\/wp\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/theshrouded.com\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=90"}],"version-history":[{"count":2,"href":"https:\/\/theshrouded.com\/wp\/index.php?rest_route=\/wp\/v2\/posts\/90\/revisions"}],"predecessor-version":[{"id":92,"href":"https:\/\/theshrouded.com\/wp\/index.php?rest_route=\/wp\/v2\/posts\/90\/revisions\/92"}],"wp:attachment":[{"href":"https:\/\/theshrouded.com\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=90"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/theshrouded.com\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=90"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/theshrouded.com\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=90"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}