[1] | 1 | ''' |
---|
| 2 | Created on Jul 4, 2010 |
---|
| 3 | |
---|
| 4 | Copyright (C) 2010 ELOI SANFÈLIX |
---|
[15] | 5 | Copyright (C) 2012 Timothy D. Morgan |
---|
[1] | 6 | @author: Eloi Sanfelix < eloi AT limited-entropy.com > |
---|
[15] | 7 | @author: Timothy D. Morgan < tmorgan {a} vsecurity . com > |
---|
[1] | 8 | |
---|
| 9 | This program is free software: you can redistribute it and/or modify |
---|
| 10 | it under the terms of the GNU Lesser General Public License, version 3, |
---|
| 11 | as published by the Free Software Foundation. |
---|
| 12 | |
---|
| 13 | This program is distributed in the hope that it will be useful, |
---|
| 14 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
| 15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
---|
| 16 | GNU General Public License for more details. |
---|
| 17 | |
---|
| 18 | You should have received a copy of the GNU General Public License |
---|
| 19 | along with this program. If not, see <http://www.gnu.org/licenses/>. |
---|
| 20 | ''' |
---|
| 21 | |
---|
| 22 | import random |
---|
| 23 | import struct |
---|
[12] | 24 | import threading |
---|
| 25 | from .. import buffertools |
---|
[8] | 26 | from .Exceptions import * |
---|
[1] | 27 | |
---|
[18] | 28 | class POA: |
---|
| 29 | """This class implements padding oracle attacks given a ciphertext and |
---|
| 30 | function that acts as a padding oracle. |
---|
[1] | 31 | |
---|
[18] | 32 | The padding scheme is assumed to be PKCS#5/#7, also defined in RFC2040. |
---|
| 33 | This attack was first described in: |
---|
| 34 | "Security Flaws Induced by CBC Padding. Applications to SSL, IPSEC, |
---|
| 35 | WTLS" by Serge Vaudenay (2002) |
---|
| 36 | |
---|
[20] | 37 | POA objects are not caller thread-safe. If multiple threads need to work |
---|
[18] | 38 | simultaneously on the same ciphertext and oracle, create a |
---|
[20] | 39 | separate instance. POA objects can execute tasks internally using |
---|
| 40 | multiple threads, however. |
---|
[18] | 41 | |
---|
| 42 | """ |
---|
| 43 | |
---|
| 44 | ## private |
---|
[12] | 45 | _thread_result = None |
---|
[15] | 46 | _oracle = None |
---|
| 47 | _ciphertext = None |
---|
| 48 | _iv = None |
---|
[18] | 49 | |
---|
| 50 | ## protected (reading ok, changing not ok) |
---|
| 51 | block_size = None |
---|
| 52 | |
---|
| 53 | ## public (r/w ok) |
---|
[43] | 54 | retries = 2 |
---|
[18] | 55 | decrypted = None |
---|
| 56 | threads = None |
---|
[12] | 57 | log_fh = None |
---|
[15] | 58 | |
---|
[18] | 59 | def __init__(self, oracle, block_size, ciphertext, iv=None, |
---|
[43] | 60 | threads=1, decrypted=b'', log_file=None): |
---|
[18] | 61 | """Creates a new padding oracle attack (POA) object. |
---|
| 62 | |
---|
| 63 | Arguments: |
---|
| 64 | oracle -- A function which returns True if the given ciphertext |
---|
| 65 | results in a correct padding upon decryption and False |
---|
| 66 | otherwise. This function should implement the prototype: |
---|
[20] | 67 | def myOracle(ciphertext, iv): ... |
---|
[18] | 68 | If the initialization vector (iv) is unknown is not included in |
---|
| 69 | the ciphertext message, it can be ignored in the oracle |
---|
| 70 | implementation (though some limitations will result from this). |
---|
| 71 | |
---|
| 72 | block_size -- The block size of the ciphertext being attacked. |
---|
| 73 | Is almost always 8 or 16. |
---|
| 74 | |
---|
| 75 | ciphertext -- The ciphertext to be decrypted |
---|
| 76 | |
---|
| 77 | iv -- The initialization vector associated with the ciphertext. |
---|
| 78 | If none provided, it is assumed to be a block of 0's |
---|
| 79 | |
---|
| 80 | threads -- The maximum number of parallel threads to use during |
---|
| 81 | decryption. If more than one thread is used, then the oracle |
---|
| 82 | function will be called in parallel. It should implement any |
---|
| 83 | internal locking necessary to prevent race conditions where |
---|
| 84 | applicable. |
---|
| 85 | |
---|
| 86 | decrypted -- If a portion of the plaintext is already known (due |
---|
| 87 | to a prior, partially successful decryption attempt), then this |
---|
| 88 | may be used to restart the decryption process where it was |
---|
| 89 | previously left off. This argument is assumed to contain the |
---|
| 90 | final N bytes (for an N-byte argument) of the plaintext; that |
---|
[38] | 91 | is, the tail of the plaintext including the pad. |
---|
[18] | 92 | |
---|
| 93 | log_file -- A Python file object where log messages will be |
---|
| 94 | written. |
---|
| 95 | |
---|
| 96 | """ |
---|
| 97 | |
---|
[15] | 98 | if(len(ciphertext)%block_size != 0 or len(ciphertext) < block_size): |
---|
| 99 | raise InvalidBlockError(block_size,len(ciphertext)) |
---|
| 100 | if(iv != None and len(iv)%block_size != 0): |
---|
| 101 | raise InvalidBlockError(block_size,len(iv)) |
---|
[38] | 102 | if len(decrypted) > len(ciphertext): |
---|
| 103 | raise Exception #XXX: custom exception |
---|
| 104 | |
---|
[18] | 105 | self.block_size = block_size |
---|
| 106 | self.decrypted = decrypted |
---|
| 107 | self.threads = threads |
---|
[12] | 108 | self.log_fh = log_file |
---|
| 109 | |
---|
[21] | 110 | self._oracle = oracle |
---|
| 111 | self._ciphertext = ciphertext |
---|
| 112 | if iv == None: |
---|
[43] | 113 | self._iv = b'\x00'*self.block_size |
---|
[21] | 114 | else: |
---|
| 115 | self._iv = iv |
---|
[12] | 116 | |
---|
[21] | 117 | |
---|
[15] | 118 | def log_message(self, s): |
---|
[12] | 119 | if self.log_fh != None: |
---|
[15] | 120 | self.log_fh.write(s+'\n') |
---|
[12] | 121 | |
---|
| 122 | |
---|
[38] | 123 | def probe_padding(self): |
---|
[18] | 124 | """Attempts to verify that a CBC padding oracle exists and then determines the |
---|
| 125 | pad value. |
---|
| 126 | |
---|
| 127 | Returns the pad string, or None on failure. |
---|
[15] | 128 | XXX: Currently only works for PKCS 5/7. |
---|
[18] | 129 | """ |
---|
| 130 | |
---|
[38] | 131 | blocks = buffertools.splitBuffer(self._ciphertext, self.block_size) |
---|
| 132 | final = blocks[-1] |
---|
| 133 | if len(blocks) == 1: |
---|
| 134 | # If only one block present, then try to use IV as prior |
---|
| 135 | prior = self._iv |
---|
| 136 | else: |
---|
| 137 | prior = blocks[-2] |
---|
| 138 | |
---|
[15] | 139 | ret_val = None |
---|
[12] | 140 | # First probe for beginning of pad |
---|
[18] | 141 | for i in range(0-self.block_size,0): |
---|
[12] | 142 | if i == -1: |
---|
| 143 | break |
---|
[43] | 144 | tweaked = prior[i] ^ 0xFF |
---|
[12] | 145 | tweaked = struct.pack("B", tweaked) |
---|
[21] | 146 | if not self._oracle(self._ciphertext+prior[:i]+tweaked+prior[i+1:]+final, self._iv): |
---|
[12] | 147 | break |
---|
| 148 | |
---|
| 149 | pad_length = 0-i |
---|
| 150 | self.log_message("Testing suspected pad length: %d" % pad_length) |
---|
| 151 | if pad_length > 1: |
---|
[43] | 152 | # XXX: If this test case fails, we should try instead |
---|
| 153 | # lengthing the pad by one byte with all 256 values (as is |
---|
| 154 | # done in the 1-byte pad case). |
---|
| 155 | # |
---|
[12] | 156 | # Verify suspected pad length by changing last pad byte to 1 |
---|
| 157 | # and making sure the padding succeeds |
---|
[43] | 158 | tweaked = prior[-1] ^ (pad_length^1) |
---|
[12] | 159 | tweaked = struct.pack("B", tweaked) |
---|
[43] | 160 | |
---|
| 161 | #XXX: This replaces the pad bytes with spaces. The hope is |
---|
| 162 | # that any UTF-8 decoding errors that the pad bytes |
---|
| 163 | # might generate are addressed this way. It is not yet |
---|
| 164 | # well tested. An option should be added to allow other |
---|
| 165 | # bytes to be used or to turn off the behavior. |
---|
| 166 | prior = bytearray(prior) |
---|
[48] | 167 | for q in range(0-self.block_size,-1): |
---|
[43] | 168 | prior[q] = prior[q]^(pad_length^32) # space |
---|
| 169 | |
---|
[21] | 170 | if self._oracle(self._ciphertext+prior[:-1]+tweaked+final, self._iv): |
---|
[15] | 171 | ret_val = buffertools.pkcs7Pad(pad_length) |
---|
| 172 | |
---|
[12] | 173 | else: |
---|
| 174 | # Verify by changing pad byte to 2 and brute-force changing |
---|
| 175 | # second-to-last byte to 2 as well |
---|
[43] | 176 | tweaked = prior[-1] ^ (2^1) |
---|
[12] | 177 | tweaked = struct.pack("B", tweaked) |
---|
| 178 | for j in range(1,256): |
---|
[43] | 179 | guess = prior[-2] ^ j |
---|
[12] | 180 | guess = struct.pack("B", guess) |
---|
[21] | 181 | if self._oracle(self._ciphertext+prior[:-2]+guess+tweaked+final, self._iv): |
---|
[15] | 182 | # XXX: Save the decrypted byte for later |
---|
| 183 | ret_val = buffertools.pkcs7Pad(pad_length) |
---|
[12] | 184 | |
---|
[15] | 185 | return ret_val |
---|
[12] | 186 | |
---|
[1] | 187 | |
---|
[15] | 188 | # XXX: This could be generalized as a byte probe utility for a variety of attacks |
---|
| 189 | def _test_value_set(self, prefix, suffix, value_set): |
---|
[12] | 190 | for b in value_set: |
---|
[15] | 191 | if self._thread_result != None: |
---|
| 192 | # Stop if another thread found the result |
---|
[12] | 193 | break |
---|
[43] | 194 | if self._oracle(prefix+struct.pack("B",b)+suffix, self._iv): |
---|
[15] | 195 | self._thread_result = b |
---|
| 196 | break |
---|
[12] | 197 | |
---|
| 198 | |
---|
[15] | 199 | def decrypt_next_byte(self, prior, block, known_bytes): |
---|
[18] | 200 | """Decrypts one byte of ciphertext by modifying the prior |
---|
| 201 | ciphertext block at the same relative offset. |
---|
| 202 | |
---|
| 203 | Arguments: |
---|
| 204 | prior -- Ciphertext block appearing prior to the current target |
---|
| 205 | block -- Currently targeted ciphertext block |
---|
| 206 | known_bytes -- Bytes in this block already decrypted |
---|
| 207 | |
---|
| 208 | """ |
---|
| 209 | |
---|
| 210 | if(len(block)!=self.block_size): |
---|
[1] | 211 | raise InvalidBlockError |
---|
| 212 | numKnownBytes = len(known_bytes) |
---|
| 213 | |
---|
[18] | 214 | if(numKnownBytes >= self.block_size): |
---|
[1] | 215 | return known_bytes |
---|
| 216 | |
---|
[18] | 217 | prior_prefix = prior[0:self.block_size-numKnownBytes-1] |
---|
[43] | 218 | base = prior[self.block_size-numKnownBytes-1] |
---|
[15] | 219 | # Adjust known bytes to appear as a PKCS 7 pad |
---|
| 220 | suffix = [0]*numKnownBytes |
---|
[12] | 221 | for i in range(0,numKnownBytes): |
---|
[43] | 222 | suffix[i] ^= prior[0-numKnownBytes+i]^known_bytes[i]^(numKnownBytes+1) |
---|
[12] | 223 | suffix = struct.pack("B"*len(suffix),*suffix)+block |
---|
| 224 | |
---|
[43] | 225 | |
---|
| 226 | for x in range(0, 1+self.retries): |
---|
| 227 | # Each thread spawned searches a subset of the next byte's |
---|
| 228 | # 256 possible values |
---|
| 229 | self._thread_result = None |
---|
| 230 | threads = [] |
---|
| 231 | for i in range(0,self.threads): |
---|
| 232 | t = threading.Thread(target=self._test_value_set, |
---|
| 233 | args=(self._ciphertext+prior_prefix, suffix, range(i,256,self.threads))) |
---|
| 234 | t.start() |
---|
| 235 | threads.append(t) |
---|
| 236 | |
---|
| 237 | for t in threads: |
---|
| 238 | t.join() |
---|
| 239 | |
---|
| 240 | # If a byte fails to decrypt, it could be because the prior |
---|
| 241 | # block's decrypted value violates UTF-8 decoding rules, or |
---|
| 242 | # because it randomly introduced a delimiter that causes |
---|
| 243 | # problems. If retries are enabled, we insert an additional |
---|
| 244 | # random block before the prior block so that the decrypted |
---|
| 245 | # value can be changed. |
---|
| 246 | if self._thread_result == None: |
---|
| 247 | if x < self.retries: |
---|
| 248 | self.log_message("Value of a byte could not be determined. Retrying...") |
---|
| 249 | prior_prefix = bytes([random.getrandbits(8) for i in range(self.block_size)]) + prior_prefix |
---|
| 250 | else: |
---|
| 251 | break |
---|
| 252 | |
---|
[12] | 253 | if self._thread_result == None: |
---|
[20] | 254 | self.log_message("Value of a byte could not be determined. Current plaintext suffix: "+ repr(self.decrypted)) |
---|
[38] | 255 | raise Exception #XXX: custom exception |
---|
[43] | 256 | |
---|
[15] | 257 | decrypted = struct.pack("B",self._thread_result^base^(numKnownBytes+1)) |
---|
[18] | 258 | self.decrypted = decrypted + self.decrypted |
---|
[1] | 259 | # Return previous bytes together with current byte |
---|
[15] | 260 | return decrypted+known_bytes |
---|
[1] | 261 | |
---|
[12] | 262 | |
---|
[43] | 263 | def decrypt_block(self, prior, block, last_bytes=b''): |
---|
[18] | 264 | """Decrypts the block of ciphertext provided as a parameter. |
---|
| 265 | |
---|
| 266 | """ |
---|
| 267 | |
---|
| 268 | while(len(last_bytes)!=self.block_size): |
---|
[15] | 269 | last_bytes = self.decrypt_next_byte(prior, block, last_bytes) |
---|
[35] | 270 | |
---|
| 271 | self.log_message("Decrypted block: %s" % repr(last_bytes)) |
---|
[15] | 272 | return last_bytes |
---|
[12] | 273 | |
---|
[15] | 274 | |
---|
| 275 | def decrypt(self): |
---|
[20] | 276 | """Decrypts the previously supplied ciphertext. If the IV was |
---|
| 277 | not provided, it assumes a IV of zero bytes. |
---|
[15] | 278 | |
---|
[18] | 279 | """ |
---|
| 280 | |
---|
[20] | 281 | if len(self.decrypted) == 0: |
---|
[38] | 282 | # First decrypt the padding (quick to decrypt and good sanity check) |
---|
| 283 | pad_bytes = self.probe_padding() |
---|
[21] | 284 | if pad_bytes == None: |
---|
| 285 | # XXX: custom exception |
---|
| 286 | raise Exception |
---|
[38] | 287 | |
---|
| 288 | self.decrypted = pad_bytes |
---|
[21] | 289 | |
---|
[15] | 290 | |
---|
[38] | 291 | # Start where we left off last, whether that be with just a pad, |
---|
| 292 | # or with additional decrypted blocks. |
---|
[15] | 293 | |
---|
[38] | 294 | # number of bytes in any partially decrypted blocks |
---|
| 295 | num_partial = len(self.decrypted) % self.block_size |
---|
| 296 | |
---|
| 297 | # number of blocks fully decrypted |
---|
[43] | 298 | finished_blocks = len(self.decrypted) // self.block_size |
---|
[38] | 299 | |
---|
| 300 | # contents of the partial block |
---|
| 301 | partial = self.decrypted[0:num_partial] |
---|
| 302 | |
---|
| 303 | # contents of fully decrypted blocks |
---|
| 304 | decrypted = self.decrypted[num_partial:] |
---|
[1] | 305 | |
---|
[38] | 306 | blocks = buffertools.splitBuffer(self._ciphertext, self.block_size) |
---|
[20] | 307 | |
---|
[38] | 308 | # Start with the partially decrypted block at the end, and work |
---|
| 309 | # our way to the front. Don't decrypt the very first block of |
---|
| 310 | # the ciphertext yet. |
---|
| 311 | for i in range(len(blocks)-1-finished_blocks, 0, -1): |
---|
| 312 | decrypted = self.decrypt_block(blocks[i-1], blocks[i], partial) + decrypted |
---|
[43] | 313 | partial = b'' |
---|
[37] | 314 | |
---|
[38] | 315 | # Finally decrypt first block |
---|
| 316 | decrypted = self.decrypt_block(self._iv, blocks[0], partial) + decrypted |
---|
| 317 | |
---|
| 318 | # Remove the padding and return |
---|
[36] | 319 | return buffertools.stripPKCS7Pad(decrypted, self.block_size, self.log_fh) |
---|
[1] | 320 | |
---|
[12] | 321 | |
---|
[15] | 322 | def encrypt_block(self, plaintext, ciphertext): |
---|
[20] | 323 | """Encrypts a block of plaintext. This is accomplished by |
---|
| 324 | decrypting the supplied ciphertext and then computing the prior |
---|
| 325 | block needed to create the desired plaintext at the ciphertext's |
---|
| 326 | location. |
---|
| 327 | |
---|
| 328 | Returns the calculated prior block and the provided ciphertext |
---|
| 329 | block as a tuple. |
---|
| 330 | |
---|
| 331 | """ |
---|
[18] | 332 | if len(plaintext) != self.block_size or len(plaintext) != len(ciphertext): |
---|
| 333 | raise InvalidBlockError(self.block_size,len(plaintext)) |
---|
[15] | 334 | |
---|
[43] | 335 | ptext = self.decrypt_block(b'\x00'*self.block_size, ciphertext) |
---|
[15] | 336 | prior = buffertools.xorBuffers(ptext, plaintext) |
---|
| 337 | return prior,ciphertext |
---|
[1] | 338 | |
---|
[15] | 339 | |
---|
| 340 | def encrypt(self,plaintext): |
---|
[20] | 341 | """Encrypts a plaintext value through "CBC-R" style prior-block |
---|
| 342 | propagation. |
---|
| 343 | |
---|
| 344 | Returns a tuple of the IV and ciphertext. |
---|
| 345 | |
---|
| 346 | NOTE: If your target messages do not include an IV with the |
---|
| 347 | ciphertext, you can instead opt to encrypt a suffix of the |
---|
[21] | 348 | message and include the IV in the the middle of the ciphertext as |
---|
| 349 | if it were an encrypted block. This one block alone will decrypt |
---|
| 350 | to an uncontrollable random value, but with careful placement, |
---|
| 351 | this might be ok. |
---|
[20] | 352 | |
---|
| 353 | """ |
---|
| 354 | |
---|
[18] | 355 | blocks = buffertools.splitBuffer(buffertools.pkcs7PadBuffer(plaintext, self.block_size), |
---|
| 356 | self.block_size) |
---|
[12] | 357 | |
---|
[18] | 358 | if (len(self.decrypted) >= self.block_size |
---|
| 359 | and len(self._ciphertext) >= 2*self.block_size): |
---|
[15] | 360 | # If possible, reuse work from prior decryption efforts on original |
---|
| 361 | # message for last block |
---|
[18] | 362 | old_prior = self._ciphertext[0-self.block_size*2:0-self.block_size] |
---|
| 363 | final_plaintext = self.decrypted[0-self.block_size:] |
---|
[15] | 364 | prior = buffertools.xorBuffers(old_prior, |
---|
| 365 | buffertools.xorBuffers(final_plaintext, blocks[-1])) |
---|
[18] | 366 | ciphertext = self._ciphertext[0-self.block_size:] |
---|
[15] | 367 | else: |
---|
| 368 | # Otherwise, select a random last block and generate the prior block |
---|
[18] | 369 | ciphertext = struct.pack("B"*self.block_size, |
---|
| 370 | *[random.getrandbits(8) for i in range(self.block_size)]) |
---|
[15] | 371 | prior,ciphertext = self.encrypt_block(blocks[-1], ciphertext) |
---|
| 372 | |
---|
| 373 | # Continue generating all prior blocks |
---|
| 374 | for i in range(len(blocks)-2, -1, -1): |
---|
| 375 | prior,cblock = self.encrypt_block(blocks[i],prior) |
---|
| 376 | ciphertext = cblock+ciphertext |
---|
| 377 | |
---|
| 378 | # prior as IV |
---|
[43] | 379 | return prior,ciphertext |
---|