Adding a nounce before hashing as covert channel

[Jacob Bachmeyer]

On 12/11/24 09:19, Frank Guthausen wrote:
> On Wed, 11 Dec 2024 14:26:54 +0000
> Andrew Gallagher via Gnupg-devel<gnupg-devel at gnupg.org>  wrote:
>
>> On 11 Dec 2024, at 11:33, Frank Guthausen<fg.gnupg at shimps.de>  wrote:
>>> Are there any good solutions to the problem (workflow, best
>>> practice) besides hoping the hash algorithm will prevent such an
>>> attack in reasonable time?
>> Avoiding hash collisions is the entire point of a hash algorithm. An
>> external salt doesn’t make it more difficult for an attacker to find
>> a hash collision, but it prevents an attacker from finding a *useful*
>> collision in advance.
> I understand this aspect of the problem. But assuming the document
> is a contract signed by Alice and Bob, how is the problem solved in
> a bidirectional manner? This extended problem remains open, because
> adding a nonce leads to an infinite regress.
>
> The problem is the double control of good and evil document, which
> makes it easier to generate hash collisions. This advantage for Alice
> moves to Bob when using a nonce from Bob.
>
> Usage of external salts would increase difficulty since the free choice
> is restricted to evil document. My understanding is that external salt
> is a better choice than nonce inside of the document. But I am not sure
> whether I am missing something in the chain of arguments.

You note a good, simple, technical solution:  a salt associated with 
each signature, such that Alice and Bob each sign their own nonce and 
the shared document.

For contracts, there are legal solutions.  I believe the term is 
"executed in parts" for one such arrangement, in which Alice signs her 
copy (with her nonce added) and Bob signs his copy (with his nonce added).

An extended form of that process continues with each then sending their 
signed copy to the other, counter-signing the signed copy received, and 
returning it as well.  This produces four slightly different versions of 
the same contract, due to the various nonces, but the substantive text 
should be identical.

If either party attempts to cheat by producing colliding contracts, it 
will be possible to determine which version the parties actually agreed 
on because that will be only version with all of the signatures and 
countersignatures.

Alice and Bob wish to agree on contract C:

 1.    Alice chooses N_A_1, signs {N_A_1,C} producing S_A_1, and sends
    {S_A_1,N_A_1,C} to Bob, while Bob chooses N_B_1, signs {N_B_1,C}
    producing S_B_1, and sends {S_B_1,N_B_1,C} to Alice.
 2.    Alice verifies S_B_1, chooses N_A_2, signs {N_A_2,S_B_1,N_B_1,C}
    producing S_A_2, and sends {S_A_2,N_A_2} to Bob, while Bob verifies
    S_A_1, chooses N_B_2, signs {N_B_2,S_A_1,N_A_1,C} producing S_B_2,
    and sends {S_B_2,N_B_2} to Alice.
 3.    Alice verifies S_B_2 while Bob verifies S_A_2.
 4. The pair of tuples {S_A_2,N_A_2,S_B_1,N_B_1,C} and
    {S_B_2,N_B_2,S_A_1,N_A_1,C} are the signed contract.  Both of the
    signatures in each tuple must validate.

This is a bit more complex than standard PGP signatures because of the 
need to include both the other party's signature and the contract in the 
signed data in step 2.

On a first analysis, I believe this Byzantine process works even if 
*both* parties try to cheat and can use their nonce fields to produce 
collisions on demand.


-- Jacob
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.gnupg.org/pipermail/gnupg-devel/attachments/20241211/7b7e88c2/attachment.html>