(no subject)
В результате дискуссии с R2R, заинтересовался следующим вопросом: допустим, есть сервер с базой данных своих юзеров. Сервер опознают юзеров по классическим паролям. Допустим, есть злоумышленник, который:
1. имеет доступ к базе юзеров,
2. может прослушивать коммуникации между ними и сервером.
Можно ли придумать такую криптосхему, которая не позволила бы ему залогиниться на сервере, выдав себя за иного юзера, и при этом использовала бы пароли, то есть симметричное шифрование, а не другие техники, наподобие сертификатов?
Мой ответ - нет, нельзя.
Интра:
При использовании симметричных ключей, у нас есть 3 возможных операции: шифрование, дешифрование, одностороннее хэширование. Шифрование/дешифрование - обратимые операции, одностороннее хэширование - необратимое.
Если функция включает в себя только шифрование/дешифрование - она обратима: если мы знаем B = F(A,K), то можем найти A = F'(B,K), где K - ключ.
Если функция включает в себя одностороннее хэширование - она необратима: если мы знаем B = F(A), то мы не можем найти A = F'(B), и при этом мы не можем найти другой A', который дал бы нам тот же B = F(A').
При использовании асимметричных ключей, у нас шифрование производится по одному ключу, а дешифрование по другому и наоборот: если B = F(A,P1), то A = F'(B,P2). То есть, "необратимая" функция, созданная одним ключом, может быть обратима только при наличии другого ключа.
Обозначения:
Пароль юзера, либо какая-то детерминистическая функция от него: P
Значение, присылаемое юзером: A - некая функция от пароля.
Значение, хранимое сервером: B - некая функция от пароля (возможно, другая).
Случайное значение для создания A: C
Постановка задачи:
Задача сервера: с помощью B проверить A.
Задача хакера: создать правильный A - с помощью B или нет.
Наша задача: используя симметричные ключи, придумать алгоритм, при котором A можно проверить с помощью B, но при этом, зная B, нельзя создать A. То есть, чтобы наш хакер, зная значение B для другого юзера, не мог бы со своей станции зайти на сервер как этот юзер.
Если юзер будет присылать один и тот же A, то его можно просто перехватить и пересылать заново.
Стало быть, надо, чтобы всякий раз посылался иной A, рандомальный.
Но если юзер будет генерировать рандомальный A, как функцию от пароля и какого-то случайного значения C, A=F(C,P), то серверу будет нечего с ним делать. Поэтому надо, чтобы и сервер знал значение C. Оно может создаваться клиентом и указываться серверу, или указываться сервером клиенту - второе предпочтительней, чтобы сервер мог быть уверен, что C действительно случайно. Пересылается оно открытым текстом и может быть перехвачено.
Далее, если функция F - обратима, то перехватив A и C, можно найти P (будь то пароль или детерминистическая функция от него), и тогда просто использовать его, чтобы получив новый C, создать собственный A. Значит, функция F должна быть необратима, и использовать одностороннее хэширование.
Теперь: сервер получает A, и знает B и C. Он хочет использовать их, чтобы проверить A. Стало быть, он должен использовать некую функцию V, чтобы получить одно из другого: либо A = V(B,C), либо B = V(A,C), либо C = V(A,B).
A = V(B,C) исключается: с помощью B и известного C не должно быть возможно найти A.
Допустим, B = V(A,C) - обратимая функция. Тогда мы можем найти обратную функцию A = V'(B,C), a это нарушает условие задачи. Если же она необратимая функция, значит, она использует одностороннее хэширование. А это означает, что мы требуем от клиента сгенерировать такой A, чтобы хэш его и C дал нам заранее известное значение B. А это невозможно, ибо нарушает определение одностороннего хэширования.
Аналогично с C = V(A,B). Либо существует обратная функция A = V'(C,B), что нарушает условие задачи, либо мы требуем от клиента создать A - хэш по паролю и случайному значению C, хэш которого в свою очередь даст нам C! Это тем более невозможно, и тоже нарушает определение хэша.
Что получается? Создав односторонний хэш A, мы не можем извлечь из него никакой полезной инфы для проверки пароля - на то он и односторонний. Единственное, что можно сделать: вычислить V(B,C) и сравнить с A - то есть использовать классический challenge-response. Но в таком случае тот, кто знает B, всегда может с его помощью создать A и выдать себя за юзера, которому этот B принадлежит.
Мораль: средствами симметричного шифрования задача решения не имеет.
Каким же образом её решают? С помощью асимметричного. Это возможно именно благодаря тому, что асимметричные ключи позволяют использовать особые функции, которые необратимы для одного ключа, и обратимы для другого.
Что происходит? Сервер хранит один ключ - публичный (B). Клиент хранит другой - приватный (P). Сервер посылает клиенту challenge - C. Клиент шифрует его приватным ключом: A = F(C,P). Эта функция необратима - нельзя найти P = F'(A,C). Но зато можно, используя публичный ключ B, использовать парную ей функцию V': C = V'(A,B). Если посланный и полученный C равны, значит, ключ P действительно парен ключу B, а значит, всё ok.
Именно эта схема используется в сертификатах, PGP и иных подобных технологиях.
1. имеет доступ к базе юзеров,
2. может прослушивать коммуникации между ними и сервером.
Можно ли придумать такую криптосхему, которая не позволила бы ему залогиниться на сервере, выдав себя за иного юзера, и при этом использовала бы пароли, то есть симметричное шифрование, а не другие техники, наподобие сертификатов?
Мой ответ - нет, нельзя.
Интра:
При использовании симметричных ключей, у нас есть 3 возможных операции: шифрование, дешифрование, одностороннее хэширование. Шифрование/дешифрование - обратимые операции, одностороннее хэширование - необратимое.
Если функция включает в себя только шифрование/дешифрование - она обратима: если мы знаем B = F(A,K), то можем найти A = F'(B,K), где K - ключ.
Если функция включает в себя одностороннее хэширование - она необратима: если мы знаем B = F(A), то мы не можем найти A = F'(B), и при этом мы не можем найти другой A', который дал бы нам тот же B = F(A').
При использовании асимметричных ключей, у нас шифрование производится по одному ключу, а дешифрование по другому и наоборот: если B = F(A,P1), то A = F'(B,P2). То есть, "необратимая" функция, созданная одним ключом, может быть обратима только при наличии другого ключа.
Обозначения:
Пароль юзера, либо какая-то детерминистическая функция от него: P
Значение, присылаемое юзером: A - некая функция от пароля.
Значение, хранимое сервером: B - некая функция от пароля (возможно, другая).
Случайное значение для создания A: C
Постановка задачи:
Задача сервера: с помощью B проверить A.
Задача хакера: создать правильный A - с помощью B или нет.
Наша задача: используя симметричные ключи, придумать алгоритм, при котором A можно проверить с помощью B, но при этом, зная B, нельзя создать A. То есть, чтобы наш хакер, зная значение B для другого юзера, не мог бы со своей станции зайти на сервер как этот юзер.
Если юзер будет присылать один и тот же A, то его можно просто перехватить и пересылать заново.
Стало быть, надо, чтобы всякий раз посылался иной A, рандомальный.
Но если юзер будет генерировать рандомальный A, как функцию от пароля и какого-то случайного значения C, A=F(C,P), то серверу будет нечего с ним делать. Поэтому надо, чтобы и сервер знал значение C. Оно может создаваться клиентом и указываться серверу, или указываться сервером клиенту - второе предпочтительней, чтобы сервер мог быть уверен, что C действительно случайно. Пересылается оно открытым текстом и может быть перехвачено.
Далее, если функция F - обратима, то перехватив A и C, можно найти P (будь то пароль или детерминистическая функция от него), и тогда просто использовать его, чтобы получив новый C, создать собственный A. Значит, функция F должна быть необратима, и использовать одностороннее хэширование.
Теперь: сервер получает A, и знает B и C. Он хочет использовать их, чтобы проверить A. Стало быть, он должен использовать некую функцию V, чтобы получить одно из другого: либо A = V(B,C), либо B = V(A,C), либо C = V(A,B).
A = V(B,C) исключается: с помощью B и известного C не должно быть возможно найти A.
Допустим, B = V(A,C) - обратимая функция. Тогда мы можем найти обратную функцию A = V'(B,C), a это нарушает условие задачи. Если же она необратимая функция, значит, она использует одностороннее хэширование. А это означает, что мы требуем от клиента сгенерировать такой A, чтобы хэш его и C дал нам заранее известное значение B. А это невозможно, ибо нарушает определение одностороннего хэширования.
Аналогично с C = V(A,B). Либо существует обратная функция A = V'(C,B), что нарушает условие задачи, либо мы требуем от клиента создать A - хэш по паролю и случайному значению C, хэш которого в свою очередь даст нам C! Это тем более невозможно, и тоже нарушает определение хэша.
Что получается? Создав односторонний хэш A, мы не можем извлечь из него никакой полезной инфы для проверки пароля - на то он и односторонний. Единственное, что можно сделать: вычислить V(B,C) и сравнить с A - то есть использовать классический challenge-response. Но в таком случае тот, кто знает B, всегда может с его помощью создать A и выдать себя за юзера, которому этот B принадлежит.
Мораль: средствами симметричного шифрования задача решения не имеет.
Каким же образом её решают? С помощью асимметричного. Это возможно именно благодаря тому, что асимметричные ключи позволяют использовать особые функции, которые необратимы для одного ключа, и обратимы для другого.
Что происходит? Сервер хранит один ключ - публичный (B). Клиент хранит другой - приватный (P). Сервер посылает клиенту challenge - C. Клиент шифрует его приватным ключом: A = F(C,P). Эта функция необратима - нельзя найти P = F'(A,C). Но зато можно, используя публичный ключ B, использовать парную ей функцию V': C = V'(A,B). Если посланный и полученный C равны, значит, ключ P действительно парен ключу B, а значит, всё ok.
Именно эта схема используется в сертификатах, PGP и иных подобных технологиях.