Как проверить самодельную эллиптическую хеш-функцию?

Question

Я узнал, что есть хеш-функция на основе эллиптических кривых. Но как было сказано:

However, it was rejected in the beginning of the competition since a second pre-image attack was found.

Я не понял, как была устроена атака Дня Рождения Вагнера, что была найдена вторая предварительная атака. Я подумал, что это из-за того, как представляется блок в виде точки.

I.

И придумал другой способ. Так как у нас есть ECDLP (Elliptic Curve Discrete Logarithm Problem)

k * G = P

Зная k, мы легко сможем вычислить P, но не наоборот. Мы можем представить сообщение M как беззнаковое число k и, например, на кривой secp256k1 вычислить точку - это и будет значением хеш-функции.

II.

Появляется такая проблема. У нас точки замкнутые относительно операции сложения, т.е. после порядка кривой мы снова будем проходить по тем же точкам и тем же порядком. И это значит, что есть вероятность найти такое сообщение, что H(m) == H(m'), где m' - поддельное сообщение, что m' = m + c*n. А сообщения обычно могут быть больше порядка кривой, если представлять последовательность байтов как число, поэтому и коллизии ещё более вероятнее могут проявиться. Вот здесь я не уверен, я придумал, что если сообщение разбить на куски (блоки) размером не более порядка кривой, а потом вычислить точки и сложить (или просто сложить все блоки и вычислить главную точку - хеш).

III.

Здесь появляется третья проблема. Операция сложения коммутативна a + b = b + a. Тогда если изменить порядок блоков, получиться тот же хеш, хотя сообщение другое. Я подумал, как и в реализации ECOH ввести в конец блока номер его (4 байт), а также добавляю в сообщение количество блоков. Разбираю ранее упомянутую атаку, как я понял, в примере использовали то, что все разбито на блоки, и они почти никак не связаны. (Возможно это лишнее действие)

IV.

Также для сообщений, где есть \0, чтобы они не были представлены как бесконечная точка, и чтобы они были различны (b'\0' != b'\0\0'), я использую little-endian, выравниваю одной единицей (\1) и затем подходящим числом нулей.

И получился вот такой код:

from Foundation.ecc import Curve, Point
from Foundation import utils, ecc

def H(curve: Curve, message: bytes) -> Point:
    message += b'\1' # for padding last block
    message_size = curve.message_size - 1
    padding_length = len(message) + (-len(message) % message_size) # ⌈l / s⌉ * s
    message = message.ljust(padding_length, b'\0') # fill to upper limit

    chunks = utils.chunks(message, message_size)
    length = utils.ui2o(len(chunks), curve.padding_size // 2)
    return curve.get_public_key(sum(
        utils.o2ui(chunk + utils.ui2o(number, curve.padding_size // 2) + length)
        for number, chunk in enumerate(chunks)
    ))

message = '''...'''.encode('utf-8') # На третий день рождества Николай обедал дома,
что в последнее...

print('Hash #1:', H(ecc.secp256k1, message)) # secp256k1 - bitcoin curve
print('Hash #2:', H(ecc.secp256k1, b''))

# file: ecc.py

@dataclass(frozen=True, slots=True)
class Point:
    """Точка с координатами x, y."""
    x: int
    y: int

@dataclass(frozen=True, slots=True)
class Curve:
    """Эллиптическая кривая (уравнение Вейерштрасса)."""
    A: int
    B: int
    F: int
    n: int
    G: Point

    @property
    def size(self) -> int:
        """Размер кривой в байтах."""
        return utils.size_in_bytes(self.F)

    @property
    def padding_size(self) -> int:
        """Кол-во байтов для заполения."""
        return 8

    @property
    def message_size(self) -> int:
        """Максимальный размер сообщения для кривой."""
        return self.size - self.padding_size

    def add_point(self, P: Point | None, Q: Point | None) -> Point | None:
        """Сложение двух разных точек на кривой, учитывая бесконечную точку."""

    def sub_point(self, P: Point | None, Q: Point | None) -> Point | None:
        """Вычитание двух разных точек на кривой, учитывая бесконечную точку."""

    def double_point(self, P: Point | None) -> Point | None:
        """Удвоение одной точки на кривой, учитывая бесконечную точку."""

    def neg_point(self, P: Point | None) -> Point | None:
        """Инверсия/Отрицание точки на кривой, учитывая бесконечную точку."""

    def mul_point(self, P: Point | None, scalar: int) -> Point | None:
        """Умножение точки на целое число (скалярное умножение), учитывая бесконечную точку."""

    def get_public_key(self, private_key: int) -> Point:
        """Создайте публичный ключ из приватного ключа.
        NOTE: Точка на кривой в конечном поле."""
        public_key = self.mul_point(self.G, private_key)
        assert public_key, 'Invalid private_key.'
        return public_key


secp256k1 = Curve(
    A=0x0,
    B=0x7,
    F=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,
    n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,
    G=Point(
        0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
        0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8,
    )
)


# file: utils.py

def ui2o(number: int, size: int = 1) -> bytes:
    """Преобразует целое число без знака в бинарную строку заданной длины. (little-endian)"""
    return number.to_bytes(size, byteorder='little', signed=False)


def o2ui(number: bytes) -> int:
    """Преобразует бинарную строку в целое число без знака. (little-endian)"""
    return int.from_bytes(number, byteorder='little', signed=False)


def chunks(data: bytes, size: int) -> list[bytes]:
    """Делит бинарную строку на куски заданной длины"""
    return [
        data[offset:offset+size] for offset in range(0, len(data), size)
    ]

Я хотел бы понять, есть ли в данном алгоритме какие-либо возможные уязвимости и как мне найти их.

БЛОГ НА HUSL

Как проверить самодельную эллиптическую хеш-функцию?

Ответы (0 шт):