chore(python): generate CoSi nonces randomly by default

### core/tools/trezor_core_tools/headertool.py
@@ -172,7 +172,9 @@ def cli(
 
     if privkeys:
         echo("Signing with local private keys...", err=True)
-        signature = cosi.sign_with_privkeys(digest, privkeys)
+        signature = cosi.sign_with_privkeys(
+            digest, privkeys, deterministic=bool(sign_dev_keys)
+        )
 
     if insert_signature:
         echo("Inserting external signature...", err=True)

### core/translations/cli.py
@@ -329,7 +329,7 @@ def gen(signed: bool, version_str: str | None, check: bool) -> None:
             "No matching signature found in signatures.json. Run `cli.py sign` first."
         )
 
-    signature = cosi.sign_with_privkeys(root, PRIVATE_KEYS_DEV)
+    signature = cosi.sign_with_privkeys(root, PRIVATE_KEYS_DEV, deterministic=True)
     sigmask = 0b111
     build_all_blobs(all_blobs, tree, sigmask, signature)
 

### python/.changelog.d/+cosi-nonces.changed
@@ -0,0 +1 @@
+CoSi nonces are now generated randomly by default. Deterministic nonce derivation is persisted, it is safe for publicly known keys only.

### python/src/trezorlib/cosi.py
@@ -14,7 +14,10 @@
 # You should have received a copy of the License along with this library.
 # If not, see <https://www.gnu.org/licenses/lgpl-3.0.html>.
 
-from collections.abc import Iterable, Sequence
+from __future__ import annotations
+
+import os
+import typing as t
 from functools import reduce
 
 from . import _ed25519
@@ -26,15 +29,15 @@
 Ed25519Signature = bytes
 
 
-def combine_keys(pks: Iterable[Ed25519PublicPoint]) -> Ed25519PublicPoint:
+def combine_keys(pks: t.Iterable[Ed25519PublicPoint]) -> Ed25519PublicPoint:
     """Combine a list of Ed25519 points into a "global" CoSi key."""
     P = [_ed25519.decodepoint(pk) for pk in pks]
     combine = reduce(_ed25519.edwards_add, P)
     return Ed25519PublicPoint(_ed25519.encodepoint(combine))
 
 
 def combine_sig(
-    global_R: Ed25519PublicPoint, sigs: Iterable[Ed25519Signature]
+    global_R: Ed25519PublicPoint, sigs: t.Iterable[Ed25519Signature]
 ) -> Ed25519Signature:
     """Combine a list of signatures into a single CoSi signature."""
     S = [_ed25519.decodeint(si) for si in sigs]
@@ -43,11 +46,8 @@ def combine_sig(
     return Ed25519Signature(sig)
 
 
-def get_nonce(
-    sk: Ed25519PrivateKey, data: bytes, ctr: int = 0
-) -> tuple[int, Ed25519PublicPoint]:
-    """Calculate CoSi nonces for given data.
-    These differ from Ed25519 deterministic nonces in that there is a counter appended at end.
+def get_nonce() -> tuple[int, Ed25519PublicPoint]:
+    """Generate a random CoSi nonce.
 
     Returns both the private point `r` and the partial signature `R`.
     `r` is returned for performance reasons: :func:`sign_with_privkey`
@@ -56,6 +56,32 @@ def get_nonce(
     `R` should be combined with other partial signatures through :func:`combine_keys`
     to obtain a "global commitment".
     """
+    # r = random512 mod l
+    # R = rB
+    # Same construction as ed25519_cosi_commit() in crypto/ed25519-donna/ed25519.c
+    r = _ed25519.decodeint(os.urandom(64)) % _ed25519.l
+    R = _ed25519.scalarmult(_ed25519.B, r)
+    return r, Ed25519PublicPoint(_ed25519.encodepoint(R))
+
+
+def _get_deterministic_nonce(
+    sk: Ed25519PrivateKey, data: bytes, ctr: int = 0
+) -> tuple[int, Ed25519PublicPoint]:
+    """Calculate a deterministic CoSi nonce for given data.
+    This differs from Ed25519 deterministic nonces in that there is a counter appended
+    at end.
+
+    DANGER: only use this with private keys that are public knowledge, i.e. the
+    development keys. The nonce depends solely on (sk, data, ctr), but the CoSi
+    challenge depends on the global commitment, which is not known at the time the
+    nonce is generated and which is chosen by the coordinator. If the same key ever
+    signs the same data in two sessions whose global commitments differ, the two
+    partial signatures reveal the private scalar.
+
+    Use :func:`get_nonce` for anything else. See also :func:`sign_with_privkeys`.
+
+    Returns the same pair as :func:`get_nonce`.
+    """
     # r = hash(hash(sk)[b .. 2b] + M + ctr)
     # R = rB
     h = _ed25519.H(sk)
@@ -83,7 +109,7 @@ def verify(
     signature: Ed25519Signature,
     digest: bytes,
     sigs_required: int,
-    keys: Sequence[Ed25519PublicPoint],
+    keys: t.Sequence[Ed25519PublicPoint],
     mask: int,
 ) -> None:
     """Verify a CoSi multi-signature. Raise exception if the signature is invalid.
@@ -131,10 +157,24 @@ def sign_with_privkey(
     return Ed25519Signature(_ed25519.encodeint(S))
 
 
-def sign_with_privkeys(digest: bytes, privkeys: Sequence[bytes]) -> bytes:
-    """Locally produce a CoSi signature from a list of private keys."""
+def sign_with_privkeys(
+    digest: bytes, privkeys: t.Sequence[bytes], *, deterministic: bool = False
+) -> bytes:
+    """Locally produce a CoSi signature from a list of private keys.
+
+    Nonces are random by default. With `deterministic=True` the resulting signature
+    is a pure function of `(digest, privkeys)`, which is required where the signature
+    bytes are committed to a repository or compared across builds. It is only
+    safe for keys that are public knowledge, such as the development keys.
+    See :func:`_get_deterministic_nonce`.
+    """
     pubkeys = [pubkey_from_privkey(sk) for sk in privkeys]
-    nonces = [get_nonce(sk, digest, i) for i, sk in enumerate(privkeys)]
+    if deterministic:
+        nonces = [
+            _get_deterministic_nonce(sk, digest, i) for i, sk in enumerate(privkeys)
+        ]
+    else:
+        nonces = [get_nonce() for _ in privkeys]
 
     global_pk = combine_keys(pubkeys)
     global_R = combine_keys(R for _, R in nonces)

### python/src/trezorlib/testing/translations.py
@@ -87,7 +87,9 @@ def sign_blob(blob: translations.TranslationsBlob) -> bytes:
     """
     # build 0-item Merkle proof
     digest = sha256(b"\x00" + blob.header_bytes).digest()
-    signature = cosi.sign_with_privkeys(digest, common.PRIVATE_KEYS_DEV)
+    signature = cosi.sign_with_privkeys(
+        digest, common.PRIVATE_KEYS_DEV, deterministic=True
+    )
     blob.proof = translations.Proof(
         merkle_proof=[],
         sigmask=0b111,

### python/tests/test_cosi.py
@@ -118,7 +118,7 @@ def test_combine_keys():
     assert cosi.combine_keys(pubkeys) == COMBINED_KEY
 
     Rs = [
-        cosi.get_nonce(privkey, message)[1]
+        cosi._get_deterministic_nonce(privkey, message)[1]
         for privkey, _, message, _ in RFC8032_VECTORS
     ]
     assert cosi.combine_keys(Rs) == GLOBAL_COMMIT
@@ -131,7 +131,7 @@ def test_cosi_combination(keyset):
 
     # zip(*iterable) turns a list of tuples to a tuple of lists
     privkeys, pubkeys, _, _ = zip(*selection)
-    nonce_pairs = [cosi.get_nonce(pk, message) for pk in privkeys]
+    nonce_pairs = [cosi._get_deterministic_nonce(pk, message) for pk in privkeys]
     nonces, commits = zip(*nonce_pairs)
 
     # calculate global pubkey and commitment
@@ -163,7 +163,7 @@ def test_m_of_n():
     sigmask = sum(1 << i for i in signer_ids)
 
     # generate multisignature
-    nonce_pairs = [cosi.get_nonce(pk, message) for pk in signers]
+    nonce_pairs = [cosi._get_deterministic_nonce(pk, message) for pk in signers]
     nonces, commits = zip(*nonce_pairs)
     global_pk = cosi.combine_keys(signer_pubkeys)
     global_commit = cosi.combine_keys(commits)
@@ -199,3 +199,14 @@ def test_m_of_n():
         # wrong sigmask
         cosi.verify(global_sig, message, 3, pubkeys, 7)
     assert "signature does not pass verification" in e.value.args[0]
+
+
+def test_random_nonces_differ():
+    privkeys = [privkey for privkey, _, _, _ in RFC8032_VECTORS]
+    digest = hashlib.sha512(b"same digest, two sessions").digest()
+    sig_a = cosi.sign_with_privkeys(digest, privkeys)
+    sig_b = cosi.sign_with_privkeys(digest, privkeys)
+    assert sig_a != sig_b
+    global_pk = cosi.combine_keys([cosi.pubkey_from_privkey(sk) for sk in privkeys])
+    cosi.verify_combined(sig_a, digest, global_pk)
+    cosi.verify_combined(sig_b, digest, global_pk)

### tests/definitions.py
@@ -81,7 +81,9 @@ def sign_payload(
         merkle_proof.append(digest)
 
     merkle_proof = len(merkle_proof).to_bytes(1, "little") + b"".join(merkle_proof)
-    signature = cosi.sign_with_privkeys(digest, PRIVATE_KEYS_DEV[:threshold])
+    signature = cosi.sign_with_privkeys(
+        digest, PRIVATE_KEYS_DEV[:threshold], deterministic=True
+    )
     sigmask = 0
     for i in range(threshold):
         sigmask |= 1 << i