Возможно ли восстановление ключа для этого 4-раундового 64-битного шифра SPN с учетом 65 тыс. известных пар открытый тек ⇐ Python

[Anonymous]

Учитывая этот конкретный дизайн шифра и корпус известного открытого текста, существует ли криптоаналитическая или структурная слабость, которая позволяет восстанавливать или дешифровать ключ быстрее, чем методом грубой силы?
Настройка следующая:

• В mycipher.py реализован собственный шифр (8-байтовые блоки, 64-битный блочный шифр).
• Секретный мастер-ключ утерян.
• У нас есть файл данных, содержащий известные пары открытый текст-зашифрованный текст (по 16 байт каждая: 8 байт открытого текста + 8 байт зашифрованного текста).
• Существует также отдельный зашифрованный текст, который мы должны расшифровать.

Известные пары открытый текст-зашифрованный текст генерируются с использованием необработанного блочного шифрования (

Код: Выделить всё

_encrypt_block

) без CBC или IV, в то время как целевой зашифрованный текст использует CBC со случайным IV.
Вот что я пробовал до сих пор:

• Обнаружение ECB и CBC
  • Я запустил обнаружение ECB на зашифрованном тексте. Все 52 блока были уникальными.
  • Шаблоны ECB (повторяющиеся блоки) отсутствовали → зашифрованный текст нетривиально ECB.
  • Тесты обнаружения CBC вернули значение False для ECB.
• Кодовая книга ECB атака
  • Загрузили все 65 536 известных пар открытый текст-зашифрованный текст из данных.
  • Пыталась сопоставить каждый блок зашифрованного текста → совсем нет.
• Грубая сила/слабый ключ попыток
  • Проверены все правдоподобные 8-байтовые слабые ключи (все нули, все единицы, последовательности ASCII, общие шаблоны проверки).
  • Попытка частичного перебора первых 4 байтов + ограниченная вторая половина → нет совпадений ключей.
• Подходы дифференциального/линейного криптоанализа
  • Построен S-box DDT, исследованы дифференциалы с высокой вероятностью.
  • Попытка упрощенной дифференциальной атаки на 1-2 раунда.
  • Построена таблица линейной аппроксимации (LAT) → ничего убедительно.
• Другие наблюдения
  • Все блоки зашифрованного текста уникальны (без повторений).
  • Похоже, что файл данных использует внутренне ECB, но зашифрованный текст, который мы хотим расшифровать, может быть чем-то другим (возможно) CBC или IV).
  • Перебор всего 64-битного пространства ключей (2^64) невозможен даже при использовании высокопроизводительных графических процессоров.

На данный момент кажется, что восстановление ключей или полная расшифровка из предоставленных пар невозможны. Я подозреваю, что профессор намеренно спроектировал ее неразрешимой, или реальное решение может включать в себя скрытую подсказку (возможно, в структуре данных, шаблонах ASCII или в mycipher.py), а не криптоанализ.

• Выглядит ли вообще возможным восстановить ключ или расшифровать зашифрованный текст с помощью имеющихся у нас данных?
• есть ли какие-либо «хитрости» или распространенные ошибки в таких университетских задачах ECB/CBC, которые я могу упустить?
• Может ли дать что-нибудь здесь атака «встреча посередине», дифференциальная или линейная, учитывая размер блока 8 байт и дизайн S-box?

Код для mycipher.py следующий: следующее:

Код: Выделить всё

#!/usr/bin/env python
# coding=utf-8
"""
MyCipher - a toy 64-bit block cipher with a minimal CLI
======================================================

Included corpus
---------------
Alongside the cipher code, a separate binary file named **`data`** is provided.
It contains 65,536 plaintext-ciphertext pairs, generated by running:

$ python mycipher.py generate

Unfortunately, the original contents of **`secret`** (i.e., `secret.py`, which
held the encryption key used during generation) have been **lost**.  As a result,
the *data* file remains a publicly accessible corpus of known plaintext-ciphertext
pairs, but the private key that produced them is no longer available.

Quick start
-----------
Encrypt or decrypt any file using the key stored in **`secret.py`**.
If you've recovered a key, create `secret.py` with its contents:

$ python mycipher.py encrypt message.txt message.enc
$ python mycipher.py decrypt message.enc message.txt
"""

from __future__ import annotations

import argparse
import binascii
import os
import struct
from functools import reduce
from typing import List

from secret import secret  # THIS `secret.py` HAS BEEN LOST!

rcon: List[int] = [
0x8D, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A
]

sbox: List[int] = [
0x3E, 0x75, 0xC3, 0xB3, 0x14, 0xD2, 0x29, 0x42,
0x74, 0xB2, 0x98, 0x8F, 0x4B, 0x69, 0xFE, 0x01,
0x9E, 0x5F, 0x65, 0xAF, 0xBF, 0xA6, 0x24, 0x18,
0x32, 0x27, 0xBE, 0x78, 0x34, 0xF2, 0xB6, 0xB9,
0x3D, 0xE1, 0x8C, 0x26, 0x96, 0x50, 0x13, 0x6D,
0xF6, 0xFC, 0x28, 0x0D, 0x41, 0xEC, 0x7C, 0xBA,
0xD6, 0x56, 0xEB, 0x64, 0x61, 0x31, 0xC5, 0x9A,
0xB0, 0xC7, 0xFD, 0x45, 0x58, 0x70, 0x8B, 0x4D,
0xB8, 0x2D, 0x85, 0x68, 0x0F, 0x36, 0xB1, 0xF4,
0xA0, 0xA9, 0x52, 0x94, 0x49, 0x1E, 0xE5, 0x23,
0x4F, 0x89, 0x9D, 0xB4, 0xF8, 0xA3, 0xF1, 0xE7,
0x51, 0x5E, 0xA5, 0x09, 0xA2, 0xE9, 0x12, 0x55,
0xD9, 0x54, 0x07, 0x37, 0x3F, 0xAB, 0x38, 0x76,
0xED, 0x84, 0x88, 0x16, 0x5A, 0xDD, 0x67, 0xA1,
0xCD, 0x0B, 0xFF, 0x0E, 0x7A, 0x2F, 0x47, 0xC9,
0x63, 0xDC, 0x53, 0x4A, 0xAD, 0x4C, 0x90, 0x10,
0x9B, 0x7E, 0x3C, 0x60, 0x2C, 0xEA, 0x11, 0xD7,
0x6B, 0x8A, 0x9F, 0xB7, 0xFB, 0x03, 0xC6, 0x00,
0x59, 0xAA, 0x83, 0x97, 0xDB, 0x1D, 0xE6, 0x20,
0xBB, 0x7D, 0x86, 0x40, 0x0C, 0xCA, 0xA4, 0xF7,
0x19, 0xDF, 0xDE, 0x77, 0xAE, 0x43, 0x93, 0x92,
0xCE, 0x33, 0xF3, 0x35, 0x79, 0xEF, 0x44, 0x82,
0x46, 0xCB, 0xD3, 0x6F, 0x6C, 0x71, 0x08, 0x6A,
0x39, 0xF0, 0x15, 0x5D, 0x8E, 0xEE, 0xA7, 0x05,
0x80, 0x48, 0xBD, 0xC0, 0xC1, 0x5C, 0x0A, 0xCC,
0x57, 0x91, 0xBC, 0xAC, 0xE0, 0xE2, 0xCF, 0x1B,
0xDA, 0x30, 0x21, 0x1C, 0x7B, 0x06, 0x25, 0x3B,
0x04, 0x66, 0x72, 0x5B, 0x17, 0xD1, 0x22, 0x2A,
0x02, 0xC4, 0x8D, 0xD0, 0xB5, 0xF5, 0x2B, 0x4E,
0xD5, 0xD8, 0xE8, 0x2E, 0x62, 0x1A, 0xD4, 0x3A,
0x73, 0xC2, 0xC8, 0x81, 0xE3, 0xF9, 0x7F, 0x95,
0x87, 0xE4, 0x1F, 0x99, 0xFA, 0x9C, 0xA8, 0x6E
]

ptable: List[int] = [
0x00, 0x08, 0x10, 0x18, 0x20, 0x28, 0x30, 0x38,
0x01, 0x09, 0x11, 0x19, 0x21, 0x29, 0x31, 0x39,
0x02, 0x0A, 0x12, 0x1A, 0x22, 0x2A, 0x32, 0x3A,
0x03, 0x0B, 0x13, 0x1B, 0x23, 0x2B, 0x33, 0x3B,
0x04, 0x0C, 0x14, 0x1C, 0x24, 0x2C, 0x34, 0x3C,
0x05, 0x0D, 0x15, 0x1D, 0x25, 0x2D, 0x35, 0x3D,
0x06, 0x0E, 0x16, 0x1E, 0x26, 0x2E, 0x36, 0x3E,
0x07, 0x0F, 0x17, 0x1F, 0x27, 0x2F, 0x37, 0x3F
]

inv_sbox: List[int] = [0] * 256
for _idx, _val in enumerate(sbox):
inv_sbox[_val] = _idx

inv_ptable: List[int] = [0] * 64
for _idx, _val in enumerate(ptable):
inv_ptable[_val] = _idx

# ---------------------------------------------------------------------------
# Helper functions
# ---------------------------------------------------------------------------

def _s2b(data: bytes | str) -> List[int]:
h = binascii.hexlify(data.encode() if isinstance(data, str) else data).decode()
return list(map(int, f"{int(h, 16):0{8 * len(data)}b}"))

def _b2s(bits: List[int]) -> bytearray:
num = reduce(lambda x, y: (x  bytearray:
return bytearray(x ^ y for x, y in zip(a, b))

def _substitute(a: bytearray) -> bytearray:
return bytearray(sbox[x] for x in a)

def _substitute_inv(a: bytearray) -> bytearray:
return bytearray(inv_sbox[x] for x in a)

def _permutation(a: bytearray) -> bytearray:
assert len(a) == 8, "Permutation operates on 64-bit blocks"
bits = _s2b(a)
bits_perm = [_s2b(a)[ptable[i]] for i in range(64)]
return _b2s(bits_perm)

def _permutation_inv(a: bytearray) ->  bytearray:
assert len(a) == 8, "Inverse permutation operates on 64-bit blocks"
bits = _s2b(a)
bits_inv = [bits[inv_ptable[i]] for i in range(64)]
return _b2s(bits_inv)

# ---------------------------------------------------------------------------
# Cipher implementation
# ---------------------------------------------------------------------------

class MyCipher:

def __init__(self, key: bytes, key_size: int = 8, rounds: int = 4):
if len(key) != key_size:
raise ValueError(f"Key must be {key_size} bytes long (got {len(key)})")
self.key_size = key_size
self.rounds = rounds
self._init_key_schedule(bytearray(key))

def _init_key_schedule(self, key: bytearray) -> None:
roundkey = bytearray(key)
tmp = roundkey[-4:]
for i in range(1, self.rounds + 1):
tmp = tmp[1:] + tmp[:1]
tmp = bytearray(sbox[x] for x in tmp)
tmp[0] ^= rcon[i]
for _ in range(self.key_size // 4):
for k in range(4):
tmp[k] ^= roundkey[-self.key_size + k]
roundkey += tmp
self._roundkey: bytearray = roundkey

def _rk(self, idx: int) -> bytearray:
return self._roundkey[self.key_size * idx : self.key_size * (idx + 1)]

def _encrypt_block(self, block: bytes) -> bytearray:
if len(block) != self.key_size:
raise ValueError("Plaintext block must be exactly one block in size")
b = bytearray(block)
for i in range(self.rounds):
b = _addkey(b, self._rk(i))
b = _substitute(b)
if i != self.rounds - 1:
b = _permutation(b)
b = _addkey(b, self._rk(self.rounds))
return b

def _decrypt_block(self, block: bytes) -> bytearray:
if len(block) != self.key_size:
raise ValueError("Ciphertext block must be exactly one block in size")
b = bytearray(block)
b = _addkey(b, self._rk(self.rounds))
for i in reversed(range(self.rounds)):
if i != self.rounds - 1:
b = _permutation_inv(b)
b = _substitute_inv(b)
b = _addkey(b, self._rk(i))
return b

def _pad(self, data: bytes) -> bytes:
pad_len = self.key_size - (len(data) % self.key_size)
if pad_len == 0:
pad_len = self.key_size  # always pad at least one block
return data + bytes([pad_len] * pad_len)

def _unpad(self, data: bytes) -> bytes:
if not data or len(data) % self.key_size:
raise ValueError("Invalid padded data length")
pad_len = data[-1]
if pad_len == 0 or pad_len > self.key_size or data[-pad_len:] != bytes([pad_len] * pad_len):
raise ValueError("Invalid padding")
return data[:-pad_len]

def encrypt(self, plaintext: bytes, iv: bytes | None = None) -> bytes:
iv = bytearray(os.urandom(self.key_size))
padded = self._pad(plaintext)

prev = iv
out_blocks: list[bytes] = [iv]

for off in range(0, len(padded), self.key_size):
block = bytearray(padded[off:off + self.key_size])
enc = self._encrypt_block(_addkey(block, prev))
out_blocks.append(enc)
prev = enc

return b"".join(out_blocks)

def decrypt(self, ciphertext: bytes) -> bytes:
if len(ciphertext) < self.key_size * 2 or len(ciphertext) % self.key_size:
raise ValueError("Ciphertext is too short or not block-aligned")

iv, *c_blocks = [ciphertext[i:i + self.key_size]
for i in range(0, len(ciphertext), self.key_size)]

prev = bytearray(iv)
p_blocks: list[bytes] = []

for c in c_blocks:
dec = _addkey(self._decrypt_block(c), prev)
p_blocks.append(dec)
prev = bytearray(c)

return self._unpad(b"".join(p_blocks))

# ---------------------------------------------------------------------------
# CLI utilities
# ---------------------------------------------------------------------------

def _load_key() ->  bytes:
if len(secret) != 8:
raise ValueError("secret from `secret.py` must be 8 bytes")
return secret

def _cmd_generate(args: argparse.Namespace) -> None:
key = _load_key()
cipher = MyCipher(key)

with open("data", "wb") as fh:
for _ in range(65_536):
plaintext = os.urandom(8)
ciphertext = cipher._encrypt_block(plaintext)
fh.write(struct.pack("8B", *plaintext))
fh.write(struct.pack("8B", *ciphertext))
print(f"Generated data file (65,536 plaintext/ciphertext pairs)")

def _read_file(path: str) -> bytes:
with open(path, "rb") as fh:
return fh.read()

def _write_file(path: str, data: bytes) -> None:
with open(path, "wb") as fh:
fh.write(data)

def _cmd_encrypt(args: argparse.Namespace) -> None:
key = _load_key()
cipher = MyCipher(key)

plaintext = _read_file(args.infile)
ciphertext = cipher.encrypt(plaintext)
_write_file(args.outfile, ciphertext)
print(f"Encrypted '{args.infile}' → '{args.outfile}' ({len(ciphertext)} bytes)")

def _cmd_decrypt(args: argparse.Namespace) -> None:
key = _load_key()
cipher = MyCipher(key)

ciphertext = _read_file(args.infile)
plaintext = cipher.decrypt(ciphertext)
_write_file(args.outfile, plaintext)
print(f"Decrypted '{args.infile}' → '{args.outfile}' ({len(plaintext)} bytes)")

# ---------------------------------------------------------------------------
# Entry point
# ---------------------------------------------------------------------------

if __name__ == "__main__":
parser = argparse.ArgumentParser(description="Toy cipher utility (64-bit block)")
subparsers = parser.add_subparsers(dest="command", required=True)

# generate
p_gen = subparsers.add_parser("generate", help="Generate plaintext-ciphertext pairs and store them in the `data` file")
p_gen.set_defaults(func=_cmd_generate)

# encrypt
p_enc = subparsers.add_parser("encrypt", help="Encrypt a file")
p_enc.add_argument("infile", help="Path to input file to encrypt")
p_enc.add_argument("outfile", help="Path for encrypted output file")
p_enc.set_defaults(func=_cmd_encrypt)

# decrypt
p_dec = subparsers.add_parser("decrypt", help="Decrypt a file previously produced by this cipher")
p_dec.add_argument("infile", help="Ciphertext file to decrypt")
p_dec.add_argument("outfile", help="Destination for decrypted plaintext")
p_dec.set_defaults(func=_cmd_decrypt)

args_ns = parser.parse_args()
args_ns.func(args_ns)

При необходимости я могу предоставить файл данных для справки.
Заранее благодарим за любые рекомендации!

Подробнее здесь: https://stackoverflow.com/questions/798 ... known-plai