Использование механики службы обмена секретами Шамира

В эпоху, когда цифровая безопасность имеет первостепенное значение, технология Shamir's Secret Sharing (SSS) представляет собой революционную технологию, обеспечивающую надежную защиту конфиденциальных данных. Этот криптографический метод, разработанный Ади Шамиром, является не просто инструментом, но и защитой, гарантирующей, что секрет не просто скроется. но при этом безопасно делиться.

В этой статье мы углубимся в гениальную механику SSS, изучаем ее основы полиномиальной математики и ее практическое применение для защиты данных, от корпоративных секретов до личных учетных данных. В нашем случае мы сохраним учетные данные для учетной записи пользователя, то есть мнемоническую фразу.

Эта статья будет разделена на несколько удобоваримых частей. В конечном итоге мы создадим один сервис для работы с SSN, включающий в себя следующие микросервисы:

* Аутентификация: для обмена токена JWT на внутренний идентификатор. * Генератор: дает пользователю адреса, по которым он может получить части ключа. * Акции: отвечает за хранение акций. * Метаданные: отвечают за хранение другой информации, необходимой для работы

Отказ от ответственности: когда я создавал этот сервис, меня очень вдохновили эти ребята: https://web3auth.io/safeauth.html , поэтому для продакшен-разработки я бы рекомендовал их больше и использовать самописный сервис только при наличии аудита безопасности, который будет анализировать каждое ваше действие. Наша компания использует самописное решение по нескольким причинам, одна из которых заключается в том, что в условиях современной неопределенности лучше иметь собственное решение. Нас проверила компания Hallward, и я надеюсь, что вскоре мы сможем выложить в открытый доступ нашу реализацию

* В первой части (часть 0) я хочу углубиться в SSS и показать основные формулы для работы с полиномиальной математикой с использованием обычного JavaScript

* Часть 1. будет содержать работы с микросервисами авторизации и генератора. Мы заменим токен JWT пользователя на наш токен, проверим некоторые учетные данные для использования нашего сервиса и выберем, где они будут храниться общие ресурсы пользователя.

* Часть 2. В этой главе я собираюсь углубиться в часть нашего сервиса, связанную с хранилищем.

Первое и самое важное — безопасное хранение доли пользователя в блокчейне.

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

2. Принципы

Обмен секретами Шамира (SSS), разработанный Ади Шамиром в 1979 году, представляет собой криптографический метод, который делит секрет на несколько частей, известных как «доли». Фундаментальная идея SSS заключается в том, что секрет можно восстановить только при объединении достаточного количества этих акций. Вот как это работает:

1. Построение полинома. Процесс начинается с создания полинома степени d, где d на единицу меньше, чем количество долей, необходимое для восстановить секрет (известный как порог). Например, если порог равен 3, создается полином степени 2 (квадратичный полином). Секрет встроен в постоянный член полинома (коэффициент a_0), а остальные коэффициенты (от a_1 до a_d) генерируются случайным образом.
2. Генерация долей: затем полином оценивается в нескольких точках (отличных от нуля) для создания долей. Каждая доля состоит из двух частей: точки, в которой оценивается полином (значение x), и соответствующего значения полинома в этой точке (значение y). Для порога n выбирается не менее n различных точек и вычисляются соответствующие им полиномиальные значения, образуя n долей.
3. Распределение акций. Эти акции распределяются между участниками. Ни один участник не сможет восстановить тайну только своей долей.
4. Восстановление секрета. Когда необходимо восстановить секрет, объединяется минимум n общих ресурсов (в соответствии с пороговым значением). Исходный полином восстанавливается с использованием этих долей, обычно с использованием такого метода, как интерполяция Лагранжа.
5. Получение секрета. После реконструкции полинома секрет можно найти, вычислив полином по нулю, что дает постоянный член полинома — исходный секрет.

Ключевые свойства SSS:

• Гибкость порогового значения. Пороговое значение можно установить в соответствии с необходимым уровнем безопасности. Секрет можно восстановить только в том случае, если объединить пороговое количество акций.
• Безопасность: пока порог не достигнут, даже доступ к n-1 общим ресурсам не дает никакой информации о секрете, при условии, что полиномиальные коэффициенты выбраны случайным образом. и безопасно.
• Допуск на ошибки. Потеря некоторых общих ресурсов не ставит под угрозу всю систему. Секрет можно восстановить, если доступно пороговое количество акций.
• Нет единой точки отказа. Поскольку секрет не хранится в одном месте, а распределяется по нескольким общим ресурсам, риск, связанный с единственной точкой отказа, снижается.

SSS полезен, когда безопасность и надежность имеют первостепенное значение, например защита криптографических ключей, защита доступа к критически важным цифровым активам или в других случаях, которые вы можете себе представить.

Формулировка задачи

О числовых схемах: мы можем использовать разные пороговые значения , но нам нужно знать, что чем больше частей ключа мы создадим, тем больше вероятность, что хакер получит необходимое количество частей ключа и соберет исходный ключ. .

В нашем сервисе мы будем использовать следующие схемы хранения данных:

На стороне пользователя мы будем использовать схему 3-2. Это означает, что закрытый ключ будет разделен на 3 разные части с индексами. А чтобы восстановить исходный приватный ключ, нам понадобится как минимум 2 из них.

Для дальнейшего удобства предлагаю использовать следующие названия для наших 3-х частей:

• Поделиться в социальных сетях: этот общий ресурс снова будет разделен на несколько частей и сохранен между разными узлами общего доступа.
• Пользовательский общий ресурс: этот общий ресурс должен храниться на стороне пользователя (например, если мы используем браузер, это может быть localStorage или другое хранилище), и нам не нужно его шифровать.
• облако. Этот общий ресурс может быть сохранен пользователем где угодно. Мы можем представить этот общий ресурс в виде мнемонической фразы или сохранить его в Интернете, но прежде чем мы это сделаем, нам необходимо зашифровать этот общий ресурс с помощью пароля или другого метода, который позволит нам получить исходное значение общего ресурса.

Как уже говорилось, для работы с закрытым ключом пользователю достаточно только 2 из 3 общих ресурсов. Например, если у пользователя есть «общий доступ пользователя» и «общий ресурс в облаке», ему не нужно получать «общий доступ в социальных сетях» для работы, или если он выполняет восстановление на новом устройстве или в браузере, ему нужны «общий доступ в социальных сетях» и «общий доступ к облаку». облачный ресурс»

На бэкэнде для «поделиться в социальных сетях» мы будем использовать 5-3. Это значит, что мы делим социальную долю на 5 частей, и для восстановления исходного ключа нам понадобится всего 3 из них. И все они будут сохранены в разных хранилищах.

Как было сказано ранее, наш сервис построен из 4 микросервисов: Auth, Generator, Shares и Metadata.

Доли сервиса могут храниться разными участниками нашего сервиса. В идеальном мире у него должны быть разные поставщики для развертывания разных хранилищ, таких как PostgreSQL, смарт-контракт Ethereum и другие (в нашем решении мы будем использовать только смарт-контракты). Но никто не ограничен в выборе собственного хранилища.

Как это работает

Во-первых, пользователям нужен токен JWT; например, его можно взять из службы аутентификации Google или Apple.

Получив JWT, мы обмениваем его на внутренний токен JWT.

Почему так сложно? Хороший вопрос. Одной из центральных идей этого сервиса является децентрализация, которая применяется к блокчейну и сервису хранения общих ключей. Однако мы не собираемся передавать учетные данные пользователя внешним сервисам и по этой причине меняем фактические идентификаторы на внутренние. Кроме того, мы проверили учетные данные, которые разрешали ограничивать только поставщиков OAuth.

Теперь проверим, есть ли сохраненный ключ; если нет, мы предлагаем создать его. После создания одну из частей делим на пять по такому же принципу и распределяем их между сервисами и сохраняем критический индекс, другую часть сохраняем локаль, а третью часть предлагаем держать где-то пользователю (есть много вариантов как это можно сделать)

Если мы понимаем, что пользователь уже сохранил свой приватный ключ, заходим в сервис шаров и получаем список сервисов, где хранятся шары пользователя и их индексы.

Получите акции. После интерполяции Лагранжа мы имеем первую часть доли. Но мы не знаем его индекс.

Здесь нам на помощь приходит сервис метаданных, от которого на основе полученного ключа мы получим индекс этого самого ключа.

Следующий шаг — найти локально сохраненную часть или попросить пользователя предоставить ее.

Мы восстанавливаем исходный закрытый ключ, если получим необходимое количество критических частей.

Немного кода

Изначально я не планировал код для этой части статьи, но все же решил, что основные функции для работы с интерполяцией Лагранжа здесь будут смотреться очень красиво, поскольку они лежат в основе всего проекта.

export class Polynomial {
    shares: BN[];
    polynomialId: string;

    static initialize(
        privateKey: BN | Buffer | null,
        threshold: number,
    ) {
        const pk = privateKey ? privateKey : randomBytes(32);

        const shares = [new BN(pk)];

        for (let i = 1; i < threshold; i += 1) {
            const share = randomBytes(32);
            shares.push(new BN(share));
        }

        const polynomialId = keccak256(...shares.map(bn => bn.toString()));

        return new Polynomial(shares, polynomialId);
    }

    static fromShares(shares: Share[]) {
        const unsortedPoints = shares.map<PolynomialPoint>(s => ({
            x: new BN(s.shareIndex, 'hex'),
            y: new BN(s.share, 'hex'),
        }));
        const sortedPoints = pointSort(unsortedPoints);
        const polynomial = generateEmptyBNArray(sortedPoints.length);
        for (let i = 0; i < sortedPoints.length; i += 1) {
            const coefficients = interpolationPoly(i, sortedPoints);
            for (let k = 0; k < sortedPoints.length; k += 1) {
                let tmp = new BN(sortedPoints[i].y);
                tmp = tmp.mul(coefficients[k]);
                polynomial[k] = polynomial[k].add(tmp).umod(curveN);
            }
        }

        const polynomialId = keccak256(...polynomial.map(bn => bn.toString()));

        return new Polynomial(polynomial, polynomialId);
    }

    constructor(shares: BN[], polynomialId: string = '') {
        this.shares = shares;
        this.polynomialId = polynomialId;
    }

    getPrivateKey(): BN {
        return this.shares[0];
    }

    getShare(x: string | BN): Share {
        const tmpX = new BN(x, 'hex');
        let xi = new BN(tmpX);
        let sum = new BN(this.shares[0]);
        for (let i = 1; i < this.shares.length; i += 1) {
            sum = sum.add(xi.mul(this.shares[i]));
            xi = xi.mul(tmpX);
        }
        return {
            share: sum.umod(curveN)?.toString('hex')?.padStart?.(64, '0'),
            shareIndex: tmpX.toString('hex'),
            polynomialID: this.polynomialId,
        };
    }
}

const pointSort = (innerPoints: PolynomialPoint[]): PolynomialPoint[] => {
    const pointArrClone = [...innerPoints];
    pointArrClone.sort((a, b) => a.x.cmp(b.x));
    return pointArrClone;
};

const generateEmptyBNArray = (length: number): BN[] =>
    Array.from({length}, () => new BN(0));

const denominator = (i: number, innerPoints: PolynomialPoint[]) => {
    let result = new BN(1);
    const xi = innerPoints[i].x;
    for (let j = innerPoints.length - 1; j >= 0; j -= 1) {
        if (i !== j) {
            let tmp = new BN(xi);
            tmp = tmp.sub(innerPoints[j].x).umod(curveN);
            result = result.mul(tmp).umod(curveN);
        }
    }
    return result;
};

const interpolationPoly = (i: number, innerPoints: PolynomialPoint[]): BN[] => {
    let coefficients = generateEmptyBNArray(innerPoints.length);
    const d = denominator(i, innerPoints);
    if (d.cmp(new BN(0)) === 0) {
        throw new Error('Denominator for interpolationPoly is 0');
    }
    coefficients[0] = d.invm(curveN);
    for (let k = 0; k < innerPoints.length; k += 1) {
        const newCoefficients = generateEmptyBNArray(innerPoints.length);
        if (k !== i) {
            let j: number;
            if (k < i) {
                j = k + 1;
            } else {
                j = k;
            }
            j -= 1;
            for (; j >= 0; j -= 1) {
                newCoefficients[j + 1] = newCoefficients[j + 1]
                    .add(coefficients[j])
                    .umod(curveN);
                let tmp = new BN(innerPoints[k].x);
                tmp = tmp.mul(coefficients[j]).umod(curveN);
                newCoefficients[j] = newCoefficients[j].sub(tmp).umod(curveN);
            }
            coefficients = newCoefficients;
        }
    }
    return coefficients;
};

Основной класс – Polynomial, имеющий 2 статических метода:

• initialize(privateKey, Threshold): создает новый полином с указанным threshold количеством долей. Если privateKey не указан, он генерирует случайный ключ. Каждая общая папка представляет собой случайное 32-байтовое число, а polynomialId вычисляется с использованием хеша keccak256 общих акций.
• fromShares(shares): создает полином из заданных долей. Он сортирует эти общие ресурсы, выполняет полиномиальную интерполяцию и вычисляет polynomialId.

polynomialId в текущей схеме используется для создания уникального идентификатора наших общих ресурсов

И 2 метода экземпляра:

• getPrivateKey(): возвращает первый общий ресурс, который предположительно является закрытым ключом.
• getShare(x): вычисляет и возвращает определенную долю полинома по заданному входному значению x.

Вспомогательные функции:

• pointSort(innerPoints): сортирует массив объектов PolynomialPoint на основе их значений x.
• generateEmptyBNArray(length): генерирует массив объектов BN, инициализированных нулем, указанной длины.
• denominator(i,nerPoints): помощник для вычисления знаменателя в интерполяции полинома Лагранжа.
• interpolationPoly(i,nerPoints): вычисляет коэффициенты интерполяционного полинома Лагранжа для заданной точки.

Понимаю, что пока все это выглядит довольно скомканно и хаотично, но все же хоть что-то =)

Для лучшего понимания теории я рекомендую заглянуть в Википедию (или другой любимый источник информации)

Заключение

В этой статье мы поверхностно рассмотрели принцип работы будущего сервиса и определили объём работ, которые необходимо проделать в следующих статьях (ориентировочно их будет ещё две)

Увидимся в следующий раз =)

---

Оригинал