assignment thread #201527

This assignment question keeps haunting me, and the professor stubbornly refuses to give us any hint.

Given a cipher mode (here referred to as "DBC", or double block chaining) as shown in the diagrams located at the bottom of my post, a function DBC-encrypt(E,IV,p) which encrypts plaintext p using initialization vector IV and symmetric cipher E, and a function DBC-decrypt(D,IV,c) which decrypts ciphertext c using initialization vector IV and symmetric cipher D (where D is the inverse of E for a given key), prove that the following authenticated encryption scheme is not secure, given that the underlying cipher E/D is secure and IVs are unique:

AE-DBC-encrypt(E,IV,m)
    EIV <- E(IV)
    c <- DBC-encrypt(E, EIV, m || IV)
    return (EIV, c)

AE-DBC-decrypt-and-authenticate(E,EIV,c)
    plaintext <- DBC-decrypt(D, EIV, c)
    m <- all-but-last-block(plaintext)
    checksum <- last-block(plaintext)
    if checksum == D(EIV) then
        return m
    else
        return null
    end

Note that IV is not transmitted, only E(IV).


Diagrams:
data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAqIAAAGUCAAAAADLoR8CAAAAAXNCSVQI5gpbmQAAC59JREFUeNrt3X+onXUdwPHP9+zaFhq7M3NTa9gwEJUhuOyHxWADTXF/KDHoh5A4rQj7QxliKtZibuBwBkIOdyuM/jKE0GQE8w+TWAYpS2uCJUq1zfljoZNwuW9/3B+7d3NynrNz7v1+z/N6w93OHzu77/s87+fzfJ9znntvyilyDPpjcLAfevtOzAIpRcWwn1v7lGfjE0WueTOxn1P7FHYA+6LtOwGUfSg40bMv294URfGZmhHsrUUBa1H21qKAtagJx95aFPXRyd0eCmmCiPh0ejYi4tm0rNunDkq/W/uUUpr3ycvu/29ERGxbObryoe6nRWH2e+5Z0UCpLPvd6y85fXTFxkON7HO3HDXLN8SWnHO+N9Z1+9Q8x0zKn/92znlTRETc2/1zi7LPk3uhRvuJh+e92cC+0/VRNvnlRsTq2BkRsTNW9fd462E9lLo/5g8//cNFe+6I2HtHZ+zA9nT7/qjRPuKCu58fwKybHfsLN+za/8r957x0SzP73PiI3Benvpfze6fGvrk/Qhv9ux/HRTlviRtzztfH1lyjfSGj8WTs8wOxtMHn6fRylC2+8NAfI3YdumhxLeuhCa6LlyN2xNURsSaeiBrtBzfrZs9+bbzawL63K/rV8WTEk92e58vhl/HpiL2xPCIujn1V2lfLNPsXIo40uKLv6ShbFTsjdsbqitZDEf/7w4b7YlXEazEaV60Zjf1V2g941s2G/ft3xTWd7u0bvXQ/9WLtfz4+76286MgbC2t5+Xhya57/p9PiI4cPj3xl3m9OOeW9Gu0bPbFM+9s3z//rsu4/z0hPX+vCS575fT586cI+fzE9zIgmm/Ssc7/63QURowfeGd0Rb8WiKu0HFdLs2d+3ufPwsgb2I73prXrmydz1eb4Ijm7QMw8cHI04GIurtK+RGfZbb+1sW9vk2b2tRWN17Ox+KVrIemiSs2J3RDwXS6q0r3MtepQttyx4ZF0j+x7fo79s/rPPzb+szmP6ing8Ih6LKwOzzqb1S5+6ttlTOr0dZR/9wpEjX1ww99OiF/uvd8Z+9sbYL+Z9rUr7ciZ1L/YbfnD5nz/b0L7T4F+niT/Gz/R1LUWncfaGIzecsS5vXFKp/8wdURd3x+/OSCmltG/ga9FYHQ1epCtsPXTHT7+08Mvbbqt1NVf3WrS5vVua2Rdu73uX2Bdu7657FJ+pGcG+aHtTFKUfCtai7K1FAWtR9taigLWoWcfeWhTWomYE+0GsRcfvnBnsxwC3FPvhtu/he5dKugtsiL5hgn3/LpecntjPpr3LJRSORCFRQKKQKCBRQKKQKCBRSBSQKCBRSBSQKCBRSBSQKCQKSBSQKCQKSBQSBSQKSBQSBSQKjDPSvi+53z82LbM3RWGKtor+zo3E3hSFyyVAooBEIVFAooBEIVFAopAoIFFAopAoIFFI1CaARIGToE23NKfpf2X2ldibonCiL4Z8gsfsi7Y3RWGKlngoZ/bV2JuiMEULPJQz+3rsTVGYouUdypl9RfamKEzR4g7lzL4me1MUhdOuHzuWJv/M7Kuxb+FtJOMPM/tK7EdaVWie3EApUmZfh32nZYUeXbkn9nXYD3OiKZ1oK9Wwl9m3YorO2FAzzy6ZfSX2w36iT+lEa/RcwcmSfSvWoimxr9q+DZdLdnPV9j28epGGpt1+rOi6fZUvse/R3hugKJyRuTl6Z+ck80HaR+dG4b8xiX2rpmjO7Ku1b8MboJl9zfYjAmVftv2wn+gnTzPHv1hcw+1C7Ic+0RnroPQh63n25dp32hLoMfculH9jMPtWXdEft52qu3W9xfYpt6bRmeeX3Lf/NPf137Fv3xX99C2TKr5Qbq19u769Llf5fT8tt/cePQpHopAoIFFIFJAoIFFIFJAoJApIFJAoJApIFJAoJApIFBIFJApIFBIFJAqJAhIFJAqJAhIFJAqJAhKFRAGJAhKFRAGJQqKARAGJQqKARAGJQqKARCFRQKKARFE1bfpl32n6X5l9JfamKJzoiyGf4DH7ou1NUZiiJR7KmX019qYoTNECD+XMvh57UxSmaHmHcmZfkb0pClO0uEM5s6/JvvI3QNOsPCmzn0N7J3oUTvW3kTSeESkP+sBn31f79k3RzL4ueyd6uKIHJAqJAhIFJAqJAhKFRIGiaNP30U97MzCzr8beFIUpWhLeoK/P3hSFyyVAorAWHbZr+sy+GntTFKaoa2L2rujhcgmQKCBRuFwqHi861WdvisIULQcvOdVob4rC5RIgUUgUkCggUUgUkCgkCkgUkCiGhurfo0/sh9zeFIUpOkhyD0d+Zl+VvSkKl0uARCFRQKKARCFRQKKQKCBRQKKQKCBRQKKQKCBRSBSQKCBRSBSQKCQKSBSQKCQKSBSQKCQKSBQSBSQKSBQSBSQKiQISBSQKiQISBSQKiQIShUQBiQIShUSBwTFiE1RCmv5XbpG9KQonevSFfILHQ28vUZii6Pcgyq2ylyhMUfR5EOV22UsUpij6O4hyy+wlClMUfR1EuW32EkXheI++HtLkn7lV9hKtaxdPPMwtspdoPfs4T+7eFCm3x95atKZ9fPS6I7XHXqLF7tZ0on1cQ6N9tJdoJbt55rkxt8heojXs5uOvMHIFp/o+2Uu0olnUTnuJirRw+5Tbtsf7vI6bu4ByS+xNURSOl+5naRo0nt7pgz7N0f8ltcbeFK3gKMittjdFh2VMD629RAVauL0TfQ0nyeNf6q7hZqc+2Uu0klVc+pCrkeG2l2gVu/iYOy/Kv625j/YSrWZVlyoqtJ/2Lpdq2ctpfC/X+cMbT8ZeovVMolTxZf5J2Eu0stNlbp29tSgKR6KQKCBRSBSQKCBRSBSQKCQKSBSQKCQKSBSQKCQKSBTDTQvvuk/sTVHAFD0J/AwaUxSQKCQKSBSQKCQKSBQSBSQKSBQSBSQKSBQSBSQKiQISBSQKiQISBSQKiQIShUQBiQISRY2kFv0Alhk/sSuzr8TeFIUTfTHkmsdQe+1NUZiiJR7KmX019qYoTNECD+XMvh57UxSmaHmHcmZfkb0pClO0uEM5s6/JvvY3QFPkhh/jG6vJc9jPqX37TvS56V5Lif1c2qf2/R6fXoYF+zk8SWb5sC/a3hU9Sj8UnOjNurLtTVGYomYEe2tRmKLWouytRQFrUfbWooBEZ9LgTd/Hrlt+6me+sSsiYtvK0ZUPdT8tUln2e+5Z0UCpLPvd6y85fXTFxkON7HM7ePfbUxs2b4qIiHu7fWoB22i6fZ56UKH9xIPz3mxgX3miXe+A78Wi7XsOvTC2Iud/dzpjB7ankX1V2ud8wd3PFzFZerG/cMOu/a/cf058q8nnaUeiL51y2suTj7fEjTnn62NrlfaljMaTsM8PxNIGn6cla9GfHP7OuZOPd8TVEbEmnqhmNTfdvvF1d4H2a+PVBvYtuaL/W1w79XhvLI+Ii2NflfZ1b/txXog40por+m5nxN/jU1OPX4vRuGrNaOzv/5XrLNgP8Lp7tuzfvyuu6XRvP9KOKbo3PjH1+GCcFkfSx+KtKu3r3vYREXHn0/O3eF30WM6KA1OPR+Od2PHbt2NRNau56fb1rUWPtb9vc+fhZdaix7Is/jn1+Mw4GBEHY3GV9nVv+4jYemtn29omz2/JWvT8eHTaUb07Ip6LJdWs5qbb17cWnWm/5ZYFj6xrZN+SKfr9kQenXue4Ih6PiMfiyirt6972sWn90qeubXyUtYKb4vSxF9998eFLc/5XpzP2+vY0b289byFOs2+qVJb9j+Ly15u+PdCWW5oP3fzziUMyYuOdERGbb+v2hDb3t8xNt5/6zQa5QvuptcHeJV3bt+d+0Ud/vfsfZ3/u5s9HxIO/+svyb95Uq32zRMuyb5pohFua2Rdv73uXhFS4vbvuUXqmTvTsy7Y3RWGKWouytxaFKWpGsLcWBaxFzTprUcAUNeGsRavbUmnwH+zn0L7yb6/L7Ife3uUSCsflEgrn/2/c7K1CwDqgAAAAAElFTkSuQmCC

data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAqIAAAGUCAAAAADLoR8CAAAAAXNCSVQI5gpbmQAADCRJREFUeNrtnV+MVOUZh3/f7ODSYMssJC5gJbJRa8UQE4i19IIWEmsNpEoNN8ULUqBtmt6gpCHU0KLgJhCgiWkkLDc09sbGamwNF8KFthXphWQVCwmVYLS7K7SiBSS7lbcXu7OzC6w5Z3b+fO98z5MAY8I4z855znu+c87sEizIVO9f9QP7lrcvqAGEIMdg31z7YI14IZnntwn7ptoHsQGwj9q+IIC4dwUO9NjHbc8UhegzZUZgz1oUgLUo9qxFAViLMuGwZy0K/ihY1l0hjCBpXnhLkt4KXVmfWi99y74jv/zogmm3//CIJO1dUlqyL/u0iMz+xPZFOZTisu/duHBGadG2i7nsLSsVM/uRdpqZ7dDarE+1ZnPpxxX9pyVJO7J/4VHZ2+gDh/YjD277Tw77Qua9rPzlSlqmQ5J0SEtrvr/lXQ9ltd+4t6PnxMXj+xdJfZsL+8/2hE0D8mgv3bXlnfrMugbYz996ZODMnptPbchnb7n3yH5NGzQbnKb+Zu+gWe1PTbnxdPnxTq0zszXabR7tYxmNk7C3ZzQ3x+sUqtnLOudffFM6cvHuTi/rod8M/eTW8uODWi5phV6RR/u6zboG2q/S+znsqzujX6bD0uGsx/kI+IdWjj7u0wJJ96jfpb0/rrU/Ll3JcUZf1V62VIekQ1rmZj30T90y+vgjlfTgipIGXNrX8by7UfafP6GHC9ntc126H71Y+8nMto+t48q/p3u5fPyly5fby49vGBoqPtD20pQpgx7tcz0xTvtN3e3vdmV/narWopq+cPD114cWTq/x/la/GTFbZ0cfl3RBB//8X3W4tPe3Fr3afld34UBXDvsq7y4t1eHDmY/zEdClD0Yf36Tzks6r06W9P66y3/1YYe+qPM+vbi2qZTqUfSkawXroTr0wZq/ulXRMs1za+1uLjrffuWHq82vz2ldzJexSe6HQ/pmfa3Mni18+U368Y+S66C6X9v6ui46z3665R/O+TpVS35a+4+km3HrN2H/y0skD95p9WCjsP9cT2vpc2udVisv+17r/XN7iqrpHb2ZPSk95epsurKnoPyVJ6nZqf9WG8GVfuTid3T77RafyymP4r7+xWH/7pp8LH5Je+EPve3O+8fP7JD373NsLVq/3aj9+Q/iyH12+9s3K8Tp8rBb7qO353iXsI7fnU/cQfabMCOyjtmeKQuy7AmtR7FmLArAWxZ61KABrUWYd9qxFgbUoMwL7eqxFQ6j/rzq+U9i3tn3Rqhm80eB5CmFft9MlDk/YN9Ke0yWIHBIFEgUgUSBRABIFIFEgUQASBRIFIFEAEgUSBSBRABIFEgUgUSBRABIFIFEgUQASBRIFIFEAEgUSBSBRgGGK6X3Jtf6xaYY9UxSYoklR27kRsGeKAqdLACQKQKJAogAkCkCiQKIAJAokCkCiACQKJApAokCivAVAogCToMhb4IQw9g9LyJ4pChzooSbYBI9b3p5EgSkKtR5ElpQ9iQJTFGo8iCwtexIFpijUdhBZYvYkCkxRqOkgstTsSRQih3v0fgjl3y0pexL1tYlHHlpC9iTqZxtbefMGBUvHnrWop21cOe8I6diTaLSbNUy0jT00WkN7EnWymccfGy0hexL1sJmvPcMwB4f6GtmTqKNZlKY9iRJp5PZcdGrcSe1knhpq8P9xas8UhchhijaMnGfh4XpPrpx5hGTsmaIO2rak7ZmiLTZ8W8+eRAk0cnsO9B4Oktde6vbwYaca2ZOok1Vc+IKzkda2J1EXm/iqT17E/7HmGtqTqJtVXXBUaC3tOV3yspXD8Fb2+cMbJ2NPon4mUXB8mj8JexJ1dri05OxZi0LkkCiQKACJAokCkCgAiQKJApAokCgAiQKQKJAoAIkCkCiQKACJAokCkCgAiQKJApAokCgAiQKQKJAoAIkCkCiQKACJAokCkCgAiQKJApAokCgAiQKQKJAoAIkCkCiQKACJAokCkCgAiYJrUvrHvsPYPwx7J/ZMUeBAHw02wWPso7ZnigJTNMZd2bB3Y88UBaZohLuyYe/HnikKTNH4dmXD3pE9UxSYotHtyoa9J3vnN0BDQ55k2DfRngM9RI77j5HknhHB6r3jY19T+/SmqGHvy54DPXBGD0CiQKIAJApAokCiACQKJApAos0ihNBx7+o/Yu/KPuS/JxUiuguXz2XkfvVDz3bW7jWyGlzv72Gf5XVT+9T9J8f2zXnxZ9g7sk9sipqkT+8YeOM+l3MoTfsET5e+8rh6sPdjn+IZ/RK9h70f+xQTnaPT2PuxT3AtqsH2qZ+5Xc2lZ5/iFD2nTuz92KeY6Ieah70f+xQTfc31Rk7OPsXrol/r/+tit6u59OxTm6Kf9vZ8vf+hxdj7sS+mVWiQpOW/xd6RfWKJavrtd6z8Afae7JNKlJ/y4NGejzRD5JAokCgAiQKJApAoAIkCiQKQKJAoAIkCZMf9PfqAfYvbM0WBKVpPfH/PAPZMUeB0CYBEgUQBSBSARIFEAUgUgESBRAFIFEgUgEQBSBRIFIBEAUgUSBSARIFEAUgUgESBRAFIFEgUgEQBSBRIFIBEAUgUSBSARIFEAUgUgESBRAFIFEgUgEQBSBRIFIBEAUgUSBSARIFEAZpLMaGvNYz9w7B3Ys8UBQ700WATPMY+anumKDBFY9yVDXs39kxRYIpGuCsb9n7smaLAFI1vVzbsHdkzRYEpGt2ubNh7smeKQuQUk/pqQ/l3w96NfYIfIxl+aNg7sS8mVaiV36CgYNj7sC8kVmhl5R6w92HfyomGMNG75GErY5/EFB33Ro0/uhj2Tuxb/UAfwkRrdHNwsMQ+ibVoCNi7tk/hdInN7Nq+iqsXoWXarcWKLmBfZ3tugELkFJuz9zbmIHM97craPTR0GuS+I4R9UlPUDHu39incADXsPdsXCRT7uO1b/UBfPsxce7HYw8eFsG/5RMetg8IXrOexj9e+kEqgV312If4PBmOf1Bn9Ne+Tu4+uJ2wfLJlGxx9frOEvbthXZZ/SN4aMWbYb9m7s0/r2OnP5fT+J23OPHiKHRIFEAUgUSBSARAFIFEgUgESBRAFIFIBEgUQBSBSARIFEAUgUWptiel9ywJ4pCsAUnQT8DBqmKACJAokCkCgAiQKJApAokCgAiQKQKJAoAIkCkCiQKACJAokCkCgAiQKJApAoAIkCiQKQKJAoAIkCkCh4JCT0A1jG/cQuw96JPVMUONBHg3keQ+naM0WBKRrjrmzYu7FnigJTNMJd2bD3Y88UBaZofLuyYe/InikKTNHodmXD3pO99xugQZbz1/Cblec52DfVPsEDfd6tFgL2zbQPyf07Prm/4hDTsTVBe+eJBtf/VBb2nC5Bioe9BN8iZl1T7ZmiwBRlRmDPWhSYoqxFsWctCsBaFHvWogAkOh7LuCOHEELbV7+157Ikae+S0pJ92adFiMv+xPZFOZTisu/duHBGadG2i3nsEzldKm+nO/9+o9S9SZJ2PO7mcDzOfvi/TC7tRx7fdrQjmdOl7DPCbOgvv+o4sVnq21zYf7YnbBqo8bRojL1015Z36jDrGmM/f+uRgTN7bj61IY+9uSar/8jfe1J3m+3UOjNbo90u7XM9MU57e0Zzc7xOImvRER7VaemglktaoVfcrObG2tdv1jXOfpXez2Gf1hn97zRP6tMCSfeo36W97/d+mOPSlexPLHo/Dcq+K//v6Kt7tFT6SCU92HZAmdeiUdnnnnXx2X/+hB4uZLdP5NL92LPKG4aGig+0vTRlyqBH+0hO0ydjv6m7/d2uZKZoni0VZt/6yE+nSqWzF0oH9bE66jAt6m9fz1nXGPtd3YUDXTnsnSdazRt609nzJem8Olt0V4zcfvdjhb2r8jw7meuiFWarV9IxzarPmWsUZ9vx2u/cMPX5tbnsE7xH/139SdLL+p6g4Ty9ce5rK3PuCqncAK18nf+6Rfu+/+K6wgez8j83khOT4OsGaMVg65b7fz8z53MTTFTbfilJ3b+Qz0RDrvVpXPaja4O+WZmfm9B10VE2z3zu7QWr1zf/VKUR+fi35yPN2Eduz/cuEVLk9nzqHmLPlAM99nHbM0WBKcpaFHvWosAUZUZgz1oUgLUos461KABTlAnHWtTdOxXq/wv7Jton9L1L2Pu053QJIofTJYic/wNlc2gMmDWwzwAAAABJRU5ErkJggg==

SOME EXCEPTIONS

Not ignoring you — just thinking about it.
Good question. I enjoy these kind of cipher hacks.

what is m || IV?

>data:image/png;base64
We're imageboard now.

>>5
With some javascript you can upload even video(100 posts*10kb chunks combined=1MB) and play via canvas/video element added to the top of thread. Its not rocket science: if it fits, its possible. Any files can be encoded in base64.

The ultimate limit for a single thread is 1000*10=10MB file(though i think that depends on how shiichan decodes unicode multibyte chars)

Also, to prevent misdecoding of posts, the uploads can be secured by making a temporary secure tripcode(which is used by upload script only for a single file, it is then randomized again) and loading chunks from posts which match the secure tripcode of first post which starts the file.

>>6
thank you einstein.

Actually there is no "hard limit", if we consider that each post can represent a link to multiple posts(or posts ranges like 1-200) in multiple threads from entire shiichan like 1,2,3,76,http://dis.4chan.org/read/prog/1321898094/1-3 which can be downloaded and combined into single file, but this would take a bit more time. Shiichan stores ~19k threads each 10MB max would be about 190000mb or 190GB if used to the maximum storage capacity(if shiichan was used exclusively for this).

Of course, such posts can be also encrypted, spread into small chunks and posted into multiple forums(not only shiichan) to prevent accidental sharing(so a posted file would ask for password), increased redudancy or for additional security in the public web.

I bet some intelligence agencies also "reuse" public forums for this, as this is incredibly simple file sharing mechanism which bypasses any filters.

>>4
In cryptography, || is often used as the concatenation operator.

>>13

thank you friend

>>10
breaking up files into tiny pieces
What is this, usenet?

>>15
Usenet at least had this automated. But some simple userscript can reassemble and display the files easily.
The only thing which i'm afraid, is that may be banned for spamming so much posts.

>>1
>homework
>lithpu
>data:image/png;base64

oh why won't you just go back to /g/ already

>>16
you might get banned for posting in general

>>17
oh why won't you just learn to quote properly

>>19
oh why won't you just go back to your hugbox, autist

OK, I have a `result', as it is known in the parlance.  Bet you weren't expecting that.  But if by chance you were expecting it, it probably isn't the one you were expecting.  Because to be honest it's not very practical.

Assume that we know the plaintext, from which we can derive the value of everything in the diagram except for the final IV block, which is unguessable.

For every block of ciphertext we intercept, we can derive a pair x, y, where D(x) = y.

Let's use those pairs to construct an empty message:
Looking at the diagram, we want to find an EIV and a C0, where
D(C0) ⊕ EIV = D(EIV)
Easy enough, just go through the pairs x_i, y_i and see if we have a y_j that equalsx_i ⊕ y_i.
From the birthday paradox, we expect that we'll need around 2^{b/2 - 1} pairs to find a match, where b is the block size, in bits.
The coupon collector's problem has negligible effect at reasonable block sizes, so this is also the number of cipher blocks we must observe.

The attack thus allows us to forge a bogus message, taking Θ(2^{b/2 - 1}) in expected time, space and required cipher blocks with known plaintext.

check 'em bro

>>22
nice doubles

>>23
schöne dubletten

rpfd = ``repariert für dich'', schuchtel

If it ain't Lisp, it's crap.

if it ain't crap, it's Lisp.

If it is Lisp, it's crap.