<commit_before><?php

/*
 * http://cryptopals.com/sets/2/challenges/12/
 *
 * Byte-at-a-time ECB decryption (Harder)
 *
 * Take your oracle function from #12. Now generate a random count of random bytes and prepend this string to every plaintext. You are now doing:
 * AES-128-ECB(random-prefix || attacker-controlled || target-bytes, random-key)
 *
 * Same goal: decrypt the target-bytes.
 *
 * Stop and think for a second.
 * What's harder than challenge #12 about doing this? How would you overcome that obstacle? The hint is: you're using all the tools you already have; no crazy math is required.
 * Think "STIMULUS" and "RESPONSE".
 */

/*
 * My thoughts on what makes the challenge harder and how to overcome this:
 *
 * The random length prefix means you don't know where your chosen plaintext resides, and it may not be block aligned.
 * To overcome this I am using a sentinel value exploiting the weakness of ECB.
 *
 * A a sentinel plaintext repeated 5 times, and the same block ciphertext detected 5 times in a row gives you a marker.
 * Prepending a single sentinel plaintext to your chosen prefix will tell you when your prefix is block aligned, and
 * where abouts in the ciphertext it resides.
 *
 * All non-aligned results can be discarded and then solved the same as challenge 12 by chopping off the
 * superfluous blocks at the start.
 */

require_once '../utils/random-bytes.php';
require_once '../01-basics/07-aes-in-ecb-mode.php';
require_once '../01-basics/08-detect-aes-in-ecb-mode.php';

$lastX = 0;
function unknownStringThing($myString, $key)
{
    $unknownString = base64_decode('<KEY>');
    $x = rand(1, 128);
    global $lastX;
    $lastX = $x;
    $prefix = getRandomBytes($x);
    return encryptAES128ECB($prefix . $myString . $unknownString, $key);
}

function detectBlockSize()
{
    $samples = [];

    for ($i = 0; $i < 1000; $i++) {
        $sampleLen = strlen(unknownStringThing('a', '0123456789abcdef'));

        if (isset($samples[$sampleLen])) {
            $samples[$sampleLen]++;
        }
        else {
            $samples[$sampleLen] = 1;
        }
    }

    ksort($samples);
    $one = key($samples);
    next($samples);
    $two = key($samples);

    return $two - $one;
}

function buildDictionary($prefix, $key, $blockSize, $sentinelBlock)
{
    $sentinel = implode(range("\x00", chr($blockSize - 1)));
    $allInOneGo = $sentinel . $prefix . implode($prefix, range("\x00", "\xff"));

    $trial = unknownStringThing($allInOneGo, $key);

    while (($sentinelPos = strpos($trial, $sentinelBlock)) === false && ($sentinelPos % $blockSize === 0)) {
        $trial = unknownStringThing($allInOneGo, $key);
    }

    return array_flip(
        str_split(
            substr($trial, $sentinelPos + $blockSize, $blockSize * 256),
            $blockSize
        )
    );
}

function findSentinelBlock($key, $blockSize)
{
    do {
        $ciphertext = unknownStringThing(str_repeat(implode(range("\x00", chr($blockSize - 1))), 5), $key);
        $cipherLen = strlen($ciphertext);

        $repetitions = [];

        for ($i = 0; $i < $cipherLen; $i += $blockSize) {
            $block = substr($ciphertext, $i, $blockSize);
            $repetition = strpos($ciphertext, $block, $i + $blockSize);

            if ($repetition && $repetition % $blockSize === 0) {
                if (isset($repetitions[$block])) {
                    $repetitions[$block]++;
                }
                else {
                    $repetitions[$block] = 1;
                }
            }
        }
    }
    while (max($repetitions) !== 4);

    asort($repetitions);
    return key($repetitions);
}

function crackBlock($prefix, $key, $blockSize, $blockIndex, $sentinelBlock)
{
    $plaintext = '';
    $sentinel = implode(range("\x00", chr($blockSize - 1)));

    for ($i = 1; $i <= $blockSize; $i++) {
        $prefix = substr($prefix, 1);

        $dict = buildDictionary($prefix . $plaintext, $key, $blockSize, $sentinelBlock);
        $trial = unknownStringThing($sentinel . $prefix, $key);

        while (($sentinelPos = strpos($trial, $sentinelBlock)) === false && (($sentinelPos % $blockSize) === 0)) {
            $trial = unknownStringThing($sentinel . $prefix, $key);
        }

        $lookup = substr($trial, ($sentinelPos + $blockSize) + ($blockIndex * $blockSize), $blockSize);

        if (!isset($dict[$lookup])) {
            return $plaintext;
        }

        $char = chr($dict[$lookup]);
        $plaintext .= $char;
        print $char;

    }
    return $plaintext;
}

// don't output if we're included into another script.
if (!debug_backtrace()) {
    $key = getRandomBytes(16);

    $blockSize = detectBlockSize();
    print "Block size:\n$blockSize\n\n";

    $ecb = repeatedBlockCount(unknownStringThing(str_repeat('a', 100), '0123456789abcdef')) > 0;
    print "ECB mode:\n";
    print $ecb ? "Yes\n\n" : "No...\n\n";

    $sentinelBlock = findSentinelBlock($key, $blockSize);
    print "Sentinel:\n";
    print bin2hex($sentinelBlock) . "\n\n";

    $lastBlock = str_repeat('A', $blockSize);
    $i = 0;
    while ($lastBlock) {
        $lastBlock = crackBlock($lastBlock, $key, $blockSize, $i++, $sentinelBlock);
    }
}<commit_msg>Refactor solution 14<commit_after><?php declare(strict_types = 1);

/*
 * My thoughts on what makes the challenge harder and how to overcome this:
 *
 * The random length prefix means you don't know where your chosen plaintext resides, and it may not be block aligned.
 * To overcome this I am using a sentinel value exploiting the weakness of ECB.
 *
 * A a sentinel plaintext repeated 4 times, and the same block of ciphertext detected 2+ times in a row gives a marker.
 * Prepending a single sentinel plaintext to your chosen prefix will tell you when your prefix is block aligned, and
 * where abouts in the ciphertext it resides.
 *
 * All non-aligned results can be discarded and then solved the same as challenge 12 by chopping off the
 * superfluous blocks at the start.
 */

namespace Cryptopals\Set2\Challenge14;

use Cryptopals\Set2\Challenge13\Solution13;

class Solution14 extends Solution13
{
    protected $ecb;
    protected $ctx;
    protected $pad;

    protected function setUp(): bool
    {
        $key = random_bytes(16);

        $this->ecb = new \AES\Mode\ECB();
        $this->ctx = new \AES\Context\ECB($key);
        $this->pad = new \AES\Padding\PKCS7();

        return true;
    }

    protected function oracle(string $myString): string
    {
        $unknownString = base64_decode('<KEY>uZyBqdXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUgYnkK');

        $prefix = random_bytes(mt_rand(1, 128));
        $message = $prefix . $myString . $unknownString;

        return $this->ecb->encrypt($this->ctx, $message . $this->pad->getPadding($message));
    }

    protected function detectBlockSize(): int
    {
        $samples = [];

        for ($i = 0; $i < 1000; $i++) {
            $sampleLen = strlen($this->oracle(''));

            if (isset($samples[$sampleLen])) {
                $samples[$sampleLen]++;
            }
            else {
                $samples[$sampleLen] = 1;
            }
        }
        
        // Highest block length minus second highest block length
        ksort($samples);
        $one = key($samples);
        next($samples);
        $two = key($samples);

        return $two - $one;
    }

    protected function buildDictionary(string $prefix, int $blockSize, string $sentinelBlock): array
    {
        $sentinel = implode(range("\x00", chr($blockSize - 1)));
        $allInOneGo = $sentinel . $prefix . implode($prefix, range("\x00", "\xff"));

        $trial = $this->oracle($allInOneGo);

        while (($sentinelPos = strpos($trial, $sentinelBlock)) === false && ($sentinelPos % $blockSize === 0)) {
            $trial = $this->oracle($allInOneGo);
        }

        return array_flip(
            str_split(
                substr($trial, $sentinelPos + $blockSize, $blockSize * 256),
                $blockSize
            )
        );
    }

    protected function findSentinelBlock(int $blockSize): string
    {
        do {
            $ciphertext = $this->oracle(str_repeat(implode(range("\x00", chr($blockSize - 1))), 4));
            $cipherLen = strlen($ciphertext);

            $repetitions = [];

            for ($i = 0; $i < $cipherLen; $i += $blockSize) {
                $block = substr($ciphertext, $i, $blockSize);
                $repetition = strpos($ciphertext, $block, $i + $blockSize);

                if ($repetition && $repetition % $blockSize === 0) {
                    if (isset($repetitions[$block])) {
                        $repetitions[$block]++;
                    }
                    else {
                        $repetitions[$block] = 1;
                    }
                }
            }
        }
        while (max($repetitions) !== 3);

        asort($repetitions);
        return key($repetitions);
    }

    protected function crackBlock(string $prefix, int $blockSize, int $blockIndex, string $sentinelBlock): string
    {
        $plaintext = '';
        $sentinel = implode(range("\x00", chr($blockSize - 1)));

        for ($i = 1; $i <= $blockSize; $i++) {
            $prefix = substr($prefix, 1);

            $dict = $this->buildDictionary($prefix . $plaintext, $blockSize, $sentinelBlock);
            $trial = $this->oracle($sentinel . $prefix);

            while (($sentinelPos = strpos($trial, $sentinelBlock)) === false && (($sentinelPos % $blockSize) === 0)) {
                $trial = $this->oracle($sentinel . $prefix);
            }

            $lookup = substr($trial, ($sentinelPos + $blockSize) + ($blockIndex * $blockSize), $blockSize);

            if (!isset($dict[$lookup])) {
                return $plaintext;
            }

            $char = chr($dict[$lookup]);
            $plaintext .= $char;
        }

        return $plaintext;
    }

    protected function execute(): bool
    {
        $blockSize = $this->detectBlockSize();
        print "Block size:\n$blockSize\n\n";

        $ecb = $this->repeatedBlockCount($this->oracle(str_repeat('a', 100))) > 0;
        print "ECB mode:\n";
        print ($ecb ? "Yes\n\n" : "No...\n\n");

        $sentinelBlock = $this->findSentinelBlock($blockSize);
        print "Sentinel:\n";
        print bin2hex($sentinelBlock) . "\n\n";

        $lastBlock = str_repeat('A', $blockSize);
        $i = 0;
        while ($lastBlock) {
            $lastBlock = $this->crackBlock($lastBlock, $blockSize, $i++, $sentinelBlock);
            print $lastBlock;
        }
        print "\n";

        return true;
    }
}
{'fraction_non_alphanumeric': 0.1462955998495675, 'fraction_numerical': 0.01504324934185784, 'mean_word_length': 2.426868556701031, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 27, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7047228', 'n_tokens_mistral': 3505, 'n_tokens_neox': 3175, 'n_words': 848}