mac_contest.rb

require 'openssl'

SIZE = 128

# Preenche uma string com 0x0 em múltiplos de 128
# e divide em blocos de 128 bytes na forma de array de inteiros
def blocks(input)
  final_size = input.bytes.length + (SIZE - input.bytes.length % SIZE)
  pad_char = 0x0.chr
  input += pad_char * (final_size - input.bytes.length)

  input.bytes.each_slice(SIZE).to_a
end

# Recebey um array de arrays de inteiros representando os blocos
# e passa um XOR de um bloco sobre outro. Por ex:
# [1, 2, 3, 4, 5, 6, 7] ^ [1, 2, 3, 4, 5, 6, 8] = [0, 0, 0, 0, 0, 0, 15]
def sum(arr)
  arr.drop(1).reduce arr.first do |result, next_block|
    result = result.zip(next_block).map{|(a, b)| a ^ b }
  end
end

# Divide a entrada em blocos, passa um XOR sobre os blocos
# E encripta com um AES-CBC com uma chave e iv que não importa para o problema
# Num ataque real, o iv é de conhecimento, a chave não. O problema não envolve descobrir a chave!
def mac(input)
  cipher = OpenSSL::Cipher::AES.new(SIZE, :CBC)
  cipher.encrypt

  cipher.update(sum(blocks(input)).map(&:chr).join) + cipher.final
end


#-------------------- as funções acima NÃO PODEM ser alteradas ------

# Dado a mensagem original, e a mensagem falsa, é preciso acrescentar bytes
# ao final da mensagem falsa para que ela tenha o mesmo MAC da mensagem original.
# As funções acima foram construídas com uma vulnerabilidade que torna esse procedimento possível!
def generate_message_fake(input, original)
  # O ataque consiste em construir uma saída adequada pra essa função.
  original
end


message = 'ola mundo'
message_fake = "mensagem fake\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02\t\x0FS\f\x12\v\tOfake"


puts "A mensagem fake functiona: "
puts mac(message) == mac(message_fake)
puts "A mensage fake é diferente da original: "
puts message != message_fake

message = 'qual seria a mensagem fake para essa string?'
message_fake = generate_message_fake('Essa mensagem é falsa, mas vai se passar por autêntica!', message)

puts "A mensagem fake functiona: "
puts mac(message) == mac(message_fake)
puts "A mensage fake é diferente da original: "
puts message != message_fake

Escreva generate_messafe_fake de forma que crie uma string falsa que consiga obter a mesma assinatura MAC de uma dada mensagem.

A vulnerabilidade está na forma de calcular o MAC. A linha 33 contém um exemplo de string falsa que funciona.

@halan, depois de discutir a solução contigo, fiz esse código rapidamente, que pode ter bugs e provavelmente pode ser melhorado:

def generate_message_fake(input, original)
  # O ataque consiste em construir uma saída adequada pra essa função.
  original_blocks = blocks(original)
  fake_blocks = blocks(input)
  original_blocks.each_with_index do |block,block_index|
    pad_block = []
    original_block = block
    fake_block = fake_blocks[block_index]
    original_block.each_with_index{|val,index| pad_block << (val^fake_block[index])}
    fake_blocks << pad_block
  end
  fake_blocks.flatten.map(&:chr).join
end

message = 'qual seria a mensagem fake para essa string?'
message_fake = generate_message_fake('Essa mensagem e falsa, mas vai se passar por autentica!', message)
=> "Essa mensagem e falsa, mas vai se passar por autentica!\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x004\x06\x12\r\x00\x1E\x00\x1C\x1A\x00G\x04MM\x00N\x15\x00\v\x16\f\fF\f\n\x16\x00\x06\x00\eAS\x00S\x03\x00S\x00\x15\x00I\x1E\bM autentica!\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"

Fez, mas fez pelo caminho mais longo, bem longo. :)

Nota: se original.length >= 128 a solução acima não vai funcionar.

@halan, como eu disse, só pensei que se fake ^ bla = original então, bla = fake ^ original. Quando tiver um tempinho penso melhor hehe!

Atualizei blocks pra suportar os acentos. #sorry

@argusrocha a sua resposta tá correta. Mas o código pode ser mais simples:

https://gist.github.com/halan/77d803e9c3c882633cbcde0f4322d1fb <-- ou algo nessa linha. 👍