Sicurezza del codice a blocchi PRP (k⊕m) ⊕k
Permettere $\mathcal S=\{0,1\}^n$ essere l'insieme di bittrinsg di $n$ bit (per il parametro di sicurezza $n$). Permettere$P$ essere una permutazione pseudo-casuale pubblica di $\mathcal S$, calcolabile in modo efficiente in entrambe le direzioni.
Costruisci un codice a blocchi $E$ con messaggi e domini chiave $\mathcal S$ come $$\begin{align} E:\mathcal S\times\mathcal S\to\;&\mathcal S\\ (k,m)\mapsto\;&E(k,m)\underset{\text{def}}=P(k\oplus m)\oplus k\\ \end{align}$$ Cosa possiamo dimostrare sulla sicurezza (sotto Chosen Ciphertext Attack, o altro) di quel codice a blocchi?
Aggiornamento: è noto come la variante a chiave singola dello schema Even-Mansour. Lo schema originale ha due tasti di input e output indipendenti. L'articolo di riferimento è Una costruzione di un cifrario da una singola permutazione pseudocasuale di Shimon Even e Yishay Mansour , in Journal of Cryptology, 1997 , originariamente negli atti di Asiacrypt 1991 .
Nota: accolgo comunque un riferimento, o meglio una dimostrazione, per la variante a chiave singola.
Si può rompere (trova un pratico distinguitore $E$ per la seguente istanza candidata di $P$?
Limita a $n$ con $p=2^n+3$prime (vedere A057732 per i valori, alcuni multipli di$8$ e persino $16$). Permettere$e$ essere $3$ (risp. $5$) per dispari (o pari) $n$, che assicura $\gcd(e,p-1)=1$. Assimilare elementi di$\mathcal S$a numeri interi. Definire$$\begin{align} Q:S\to\;&\mathcal S\\ m\mapsto\;&Q(m)\underset{\text{def}}=((m+2)^e\bmod p)-2 \end{align}$$ Questa è una permutazione di $\mathcal S$, ma non un PRP abbastanza buono per l'applicazione (questo è un esercizio interessante. Suggerimento: cos'è $Q(m)+Q(2^n-1-m)$ ?)
Permettere $a$ e $b$ essere due $n$costanti -bit Nothing-Up-My-Sleeve , ad es$a=\left\lfloor\pi\,2^{n-2}\right\rfloor$ e $b=\left\lfloor2^{n-1/2}\right\rfloor$. Definire$$\begin{align} P:\mathcal S\to\;&\mathcal S\\ m\mapsto\;&P(m)\underset{\text{def}}=Q((Q(m)+a\bmod 2^n)\oplus b)\\ \end{align}$$
Razionale vago: inserire il non lineare $x\mapsto (x+a\bmod 2^n)\oplus b$ tra due istanze di $Q$ fornire la diffusione. $a\ne0$ è necessario per la sicurezza, ma per ora non ho possibilità di fuga $(a,b)=(1,0)$.
Nota: ho solo creato un sistema di sicurezza così intelligente che non riesco a immaginare un modo per infrangerlo. Il dilettante più incapace può, come osservato da Bruce Schneier. Quella seconda parte della domanda è quindi fuori tema, e capirei i voti negativi!
Risposte
Cosa possiamo dimostrare sulla sicurezza (sotto Chosen Ciphertext Attack, o altro) di quel codice a blocchi?
Questa è la costruzione a chiave unica di Even-Mansour come è stato già notato nei commenti della domanda. L'ultima analisi che ho potuto trovare di questa costruzione è di Orr Dunkelman, Nathan Keller e Adi Shamir: "Minimalism in Cryptography: The Even-Mansour Scheme Revisited" dove sostengono che qualsiasi attacco riuscito soddisfa$DT=\Omega(2^n)$ con $D$ essendo il numero di query all'oracolo di crittografia e $T$essendo il numero di query alla permutazione stessa. Ciò significa che il prodotto di questi due numeri di query scala esponenzialmente nell'ampiezza della permutazione per qualsiasi attacco con probabilità di successo costante. Questo risultato è stato dimostrato anche nel lavoro originale di Even e Mansour per la custodia a due chiavi.
Per quanto riguarda la costruzione candidata per una permutazione casuale pubblica, si dovrebbe prima notare che questo modello è molto vicino al modello dell'oracolo casuale (ma con una permutazione invece di una funzione). Ciò significa che qualsiasi costruzione candidata può offrire solo sicurezza euristica (indiretta). Tuttavia, non ho un attacco alla permutazione a portata di mano. Tuttavia questo è un modello che a volte viene utilizzato nella crittografia, ad esempio nelle applicazioni MPC, dove si userebbe AES con una chiave fissa per tali esigenze.