image

De onzichtbare backdoor: een voorspelbare PRNG in de CPU

maandag 22 juli 2013, 11:12 door Luc Gommans, 24 reacties

Onlangs verscheen er op klokkenluiderwebsite Cryptome een bericht dat de Amerikaanse inlichtingendienst NSA al het SSL/TLS-verkeer kan ontsleutelen wanneer dit is gegenereerd op een Intel processor met een Ivy Bridge architectuur of nieuwer. Security.NL-lezer Luc Gommans besloot dit uit te zoeken en schreef het volgende artikel.

Architectuur
In het derde kwartaal van 2011 is Intel begonnen met het produceren van hun nieuwe processorarchitectuur: Ivy Bridge. Deze had een aantal voordelen, waaronder verbeteringen van Intel HD Graphics, energiezuinigheid en een nieuwe instructie genaamd RdRand.

Deze RdRand instructie is een "pseudo-random number generator" (PRNG); iets dat schijnbare willekeurige getallen genereert. De mogelijkheid tot het genereren van willekeurige getallen is ontzettend belangrijk voor heel veel toepassingen. Een bekend voorbeeld is SSL/TLS, de techniek achter https, maar ook TCP sequence numbers moeten willekeurig zijn. Betrouwbare willekeurigheid is dus al vereist voor het opzetten van iets simpels als een TCP connectie.

De werking van een PRNG
Computers zijn echter niet erg creatief, en willekeurige getallen bedenken blijkt een moeilijke opgave. Er wordt dus een hybride systeem gebruikt dat van bepaalde bronnen een bepaalde hoeveelheid "ware" willekeurigheid weet te onttrekken. Bijvoorbeeld de timing van toetsaanslagen en muisbewegingen, afwijking in de temperatuursensor, of het statische geluid dat je hoort wanneer je de microfoon insteekt kunnen worden door het systeem worden gebruikt.

Deze "ware" willekeurigheid wordt vervolgens als invoer gebruikt voor een PRP-functie (pseudo random permutation), dat vervolgens ontzettend veel getallen kan genereren zonder voorspelbaar te worden. Wat een PRP dus doet is het omzetten van invoer naar willekeurige uitvoer, maar bij dezelfde invoer komt natuurlijk ook altijd dezelfde uitvoer.

Dit is in feite identiek aan de manier waarop encryptie werkt: Je hebt een wachtwoord als invoer en krijgt, als het goed is, data als uitvoer die niet te onderscheiden is van (ware) willekeurigheid. Sterker nog, het bekende encryptiealgoritme AES is niet ontworpen als encryptiealgoritme. Het is ontworpen als PRP functie! Willekeurige data kan dus als "wachtwoord" worden gebruikt voor AES, waarna AES het om kan zetten in een praktisch oneindige hoeveelheid willekeurige data (256 exabytes).

Dit werkt prima, zolang er voldoende willekeurigheid beschikbaar is als invoer voor onze PRP (dat kan AES zijn, maar ook een ander algoritme). Zeker wanneer een systeem net aan het opstarten is, wil dit nog wel eens tekort schieten. Dat Intel met een eigen willekeurige nummer generator komt is dus een welkome aanvulling voor besturingssystemen.

Implementatie van RdRand in Linux
Eind juli 2011 is in de nieuwsgroep over de Linux kernel gediscussieerd over het implementeren van de RdRand instructie in de kernel. Peter Anvin van Intel kwam met een patch (codewijziging) die RdRand implementeerde. Daarop reageerde Matt Mackall dat hij fel tegen het doorvoeren was omdat de werking niet te controleren viel zonder in een electronenmicroscoop te investeren. De data verkregen van de CPU kan best worden gebruikt en gemixt met andere bronnen van willekeurigheid (entropy), maar zou niet de bestaande bronnen moeten omzeilen en direct worden geinjecteerd in "/dev/urandom" (een bron van pseudo-willekeurigheid in Linux systemen).

Linus Torvalds, de oprichter van de Linux kernel, zei vervolgens dat zijn afwijzing niks betekende, en dat Matt niet met domme argumenten (sic) moet komen over de controleerbaarheid door middel van een electronenmicroscoop. In reactie daarop heeft Matt zijn positie opgezegd. Op 28 oktober 2011 heeft Linus Torvalds de toevoeging doorgevoerd.

De code is echter nog altijd aanwezig in de Linux kernel (/drivers/char/random.c, functie "get_random_bytes_arch"). Het is wel mogelijk om dit uit te schakelen bij het compilen van Linux, maar dit is voor een gemiddelde gebruiker niet te doen. In een comment bij de functie wordt echter wel erkend dat het onmogelijk te controleren is, en de NSA mogelijk een wachtwoord heeft waarmee de output kan worden voorspeld ("it is impossible to verify that it is implemented securely (as opposed, to, say, the AES encryption of a sequence number using a key known by the NSA)").

Closed-source
In het geval van Linux zijn de gevolgen nog enigzins beperkt. Iedereen kan wijzigingen zien en problemen ontdekken, aankaarten en veranderen. Maar in bijvoorbeeld Mac OS X of Windows is het niet mogelijk om na te gaan hoe er precies met RdRand wordt omgegaan. Het kan zijn dat Windows alsnog kwetsbaar is hiervoor.

Eigenlijk geldt hetzelfde ook voor de RdRand instructie zelf: het feit dat het closed source is maakt het al oncontroleerbaar en maakt dat wij Intel op hun blauwe ogen (of stickers) moeten geloven.

Potentiele gevolgen
Het kunnen voorspellen van de willekeurige getallen in een computer is zoals gezegd een zeer groot beveiligingsrisico. Niet alleen omdat crypografie gekraakt kan worden (bijvoorbeeld opgevangen verkeer van https verbindingen); het kan ook offensief gebruikt worden. Bijvoorbeeld DNS cache poisoning is mogelijk wanneer te voorspellen valt welke poort de DNS server gaat gebruiken om een request te doen. Zo zou het mogelijk zijn om gebruikers naar valse websites te sturen die volledig legetiem uitzien. Zelfs het adres in de adresbalk klopt.

Ook private keys worden willekeurig gegenereerd om SSL/TLS sessies mee te beveiligen. Als jouw computer geen Ivy Bridge CPU heeft, heeft de server die de private key genereerde dat misschien wel. En wanneer de private key bekend is, is het https verkeer ook te vervalsen. Bijvoorbeeld als de private key voor Gmail door Google is gegenereerd op een Ivy Bridge, kan de https connectie van Gmail worden vervalst.

Het is niet gezegd dat Intel's RdRand instructie voorspelbaar is, maar het feit dat het niet te controleren is, dat de NSA behoorlijk ver lijkt te gaan in het monitoren van verkeer, en dat Intel een Amerikaans bedrijf is dat moet luisteren naar "National Security brieven", maakt het wel een mogelijkheid.

Overigens is in een vraag op de Cryptography StackExchange website, onder andere door Orson Peters, bevestigd dat het decrypten van https mogelijk is wanneer de willekeurige-getallen-generator niet willekeurig blijkt te zijn:

Conclusie: Hopelijk kunnen we Intel's random functie vertrouwen, maar het is cryptografisch niet te controleren.

Reacties (24)
22-07-2013, 11:36 door Erik Loman
Ik las onlangs dit artikel omtrent Intel's Ivy Bridge Random Number Generator:
http://electronicdesign.com/learning-resources/understanding-intels-ivy-bridge-random-number-generator
The RNG begins with an entropy source (ES) whose behavior is determined by unpredictable thermal noise (Fig. 1).
Uit de Intel documentatie:
The ES runs asynchronously on a self-timed circuit and uses thermal noise within the silicon to output a random stream of bits at the rate of 3 GHz.
Bron: http://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide/

Hier een onderzoek (van Rambus) naar Random Number Generator in Ivy Bridge:
In conclusion, we believe the Ivy Bridge RNG is well designed, with a wide margin of safety, and the output is appropriate to use directly for cryptographic keys, secret nonces, and other sensitive values.
Bron: http://www.cryptography.com/public/pdf/Intel_TRNG_Report_20120312.pdf

Kortom: het is bekend (en onderzocht) hoe Intel aan de entropy komt en is in lijn met wat bovenstaand artikel adviseert om afwijkingen in de temperatuursensor te gebruiken als bron voor entropy.
22-07-2013, 11:40 door RickDeckardt
Toch maar een electronenmicroscoop kopen....
22-07-2013, 12:36 door spatieman
oeps, dan maar een AMD machine gebruiken (zolang die nog geen PRNG heeft)..
22-07-2013, 14:57 door Anoniem
We vertrouwen ook op Kerberos, waarvan de random number
Implementatie ook eens lek was, en altijd dezelfde reeks getallen
genereerde... Tijdje terug
22-07-2013, 15:11 door Anoniem
Door Erik Loman: Hier een onderzoek (van Rambus) naar Random Number Generator in Ivy Bridge:
In conclusion, we believe the Ivy Bridge RNG is well designed, with a wide margin of safety, and the output is appropriate to use directly for cryptographic keys, secret nonces, and other sensitive values.
Bron: http://www.cryptography.com/public/pdf/Intel_TRNG_Report_20120312.pdf

Kortom: het is bekend (en onderzocht) hoe Intel aan de entropy komt en is in lijn met wat bovenstaand artikel adviseert om afwijkingen in de temperatuursensor te gebruiken als bron voor entropy.
Quote dan wel volledig. Direct achter de zin staat dat de schrijvers aanraden een "single point of failure" te vermijden en de RdRand output te mixen met bestaande entropy bronnen:
However, the most prudent approach is always to combine any other available entropy sources to avoid having a single point of failure.

Verder geven ze ook aan geen toegang te hebben gehad tot de hardwareonderdelen en dat ze testdata hebben gebruikt die opgestuurd werd door Intel:
We did not have access to Ivy Bridge parts, so Intel provided us with testing data

Dat de CPU data genereert die alle tests passeert is geen nieuws, dat kan ik zelf ook ontwerpen (AES met als invoer een afgeleide van het serial number en oplopende teller die reboots overleeft). En toch kan ik dan, ondanks alle tests waar het voor slaagt, de output voorspellen met minimale moeite. Enkel nagaan op welk punt de teller stond is veel minder werk dan ware willekeurige uitvoer raden, en misschien is er wel apparatuur bij Intel die me de teller status kan geven voor forensische analyse.
22-07-2013, 17:26 door Anoniem
Een systeem dat gebruik maakt van (provable) true (quantum) randomness is te vinden op http://wuala.com/freemovequantumexchange

Dit systeem ondersteund open en gesloten groepen.

Open groepen zijn met name bedoeld om content filtering te voorkomen. Een voorbeeld van zo`n open groep is te vinden op http://wuala.com/pgpstore

Voor security worden gesloten groepen gebruikt. Deze werken o.a. met synchrone en asynchrone VPN`s om encrypt verkeer zoveel mogelijk onzichtbaar te maken. De dataminimalisatie procedures van de NSA schrijven namelijk voor dat encrypt verkeer onbeperkt opgeslagen wordt, zowel binnen als buiten de VS.

Voorbeelden van gebruikte protocollen bij gesloten groepen zijn te vinden op http://wuala.com/FreemoveQuantumExchange/Aspects/Security/Programs/ChannelCodingExamples/PadlockSL in het document `sharing_secrets`.
22-07-2013, 17:48 door Anoniem
Door Erik Loman: Ik las onlangs dit artikel omtrent Intel's Ivy Bridge Random Number Generator:
http://electronicdesign.com/learning-resources/understanding-intels-ivy-bridge-random-number-generator
The RNG begins with an entropy source (ES) whose behavior is determined by unpredictable thermal noise (Fig. 1).
Uit de Intel documentatie:
The ES runs asynchronously on a self-timed circuit and uses thermal noise within the silicon to output a random stream of bits at the rate of 3 GHz.
Bron: http://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide/

Hier een onderzoek (van Rambus) naar Random Number Generator in Ivy Bridge:
In conclusion, we believe the Ivy Bridge RNG is well designed, with a wide margin of safety, and the output is appropriate to use directly for cryptographic keys, secret nonces, and other sensitive values.
Bron: http://www.cryptography.com/public/pdf/Intel_TRNG_Report_20120312.pdf

Kortom: het is bekend (en onderzocht) hoe Intel aan de entropy komt en is in lijn met wat bovenstaand artikel adviseert om afwijkingen in de temperatuursensor te gebruiken als bron voor entropy.

Dat is het net niet helemaal. Het voorgestelde design is onderzocht en is inderdaad een prima methode.
Wat de twijfel is, in het licht van het vergaande NSA gluren, of het voorgestelde design ook exact zo in de Intel CPUs geïmplementeerd is.
Het hele doel van een goed cryptografisch algorithme is dat de output statistisch niet te onderscheiden is van een 'echte' random generator.
Als de output van de Intel chip op die manier pseudo random is (maar voldoende voorspelbaar door de bezitter van een geheime sleutel) is dat statistisch niet aan te tonen.

Vandaar de stelling dat zonder elektronenmicroscoop niet te valideren is of het beschreven RNG design ook volledig zo gebruikt wordt in de CPUs.

Het is onder ITers wel bekend dat documentatie en implementatie soms twee verschillende dingen zijn :-)
22-07-2013, 22:58 door Anoniem
AH mijn random.c is van 2 dec 2010 en support dit niet.
Ik wist dat het niet altijd goed is om maar met de updates mee te marcheren, kan best zijn dat er een backdoor
wordt verkocht als een "update"...
Waarom is Linus hier eigenlijk zo fel over, is hij omgekocht door de inlichtingendiensten?
23-07-2013, 09:29 door Anoniem
Voor de liefhebbers, bijgaand een bewijs dat wanneer de INTEL DRNG op de standaard manier gebruikt wordt, deze
rekenkundig veilig is van complexiteitklasse IND-CPA. Deze generator kan echter wel op een andere manier gebruikt worden, zodat je de True Randomness eruit kunt halen. Hoe je dit kunt doen staat beschreven in paragraaf 4.4 van de manual. Echter zal deze generator vrijwel altijd op de standaard manier gebruikt worden. En dan is het gewoon een pseudo-random generator.

Bijlage: Pseudo-randomness IND-CPA bewijs van de Intel DRNG

type 'a array.

op length : 'a array -> int.

op make : (int,'a) -> 'a array.

op [~>] : ('a array, int) -> 'a as aget.

op [<~] : ('a array, int * 'a) -> 'a array as aset.

axiom length_pos : forall (t:'a array), 0 <= length(t).

axiom length_make : forall (a:'a, len:int),
0 <= len => length(make(len,a)) = len.

axiom length_aset : forall (t : 'a array, i:int, a:'a),
length(t <~ (i,a)) = length(t).

axiom aget_aset_same : forall (t:'a array, i:int, a:'a),
0 <= i => i < length(t) => (t <~ (i,a)) ~> i = a.

axiom aget_aset_diff : forall (t:'a array, i,j:int, a:'a),
i <> j => ((t <~ (i,a)) ~> j) = (t ~> j).

cnst k, l : int.

axiom l_pos : 0 <= l.

type key = bitstring{k}.

type block = bitstring{l}.

op E : (key,block) -> block.

type message = block array.

type cipher = block array.

adversary A() : bool { (message, message) -> cipher }.


cnst q : int.
axiom q_pos : 0 <= q.

game CPA = {
fun KG () : key = {
var Ke : key = {0,1}^k;
return Ke;
}

fun Enc(Ke:key, m:message) : cipher = {
var p : block;
var c : cipher = make(length(m)+1,bs0_l);
var i : int = 0;
c = c <~ (i, {0,1}^l);
while (i < length(m)) {
p = (c ~>(i)) ^^ (m~>i);
i = i + 1;
c = c <~ (i, E(Ke,p));
}
return c;
}

var b : bool
var K : key
var count : int

fun LR(m0,m1:message) : cipher = {
var cb : cipher;
if (length(m0) = length(m1) && count + length(m0) <= q) {
cb = Enc(K, b ? m0 : m1);
count = count + length(m0);
} else {
cb = make(0,bs0_l);
}
return cb;
}

abs A = A {LR}

fun Main () : bool = {
var b' : bool;
K = KG();
b = {0,1};
count = 0;
b' = A ();
return b = b';
}
}.


game PRF0 = {
var K : key

fun BC (bl:block) : block = {
var be : block;
be = E(K,bl);
return be;
}

var b : bool
var count : int

fun LR(m0,m1:message) : cipher = {
var c : cipher;
var p,ci : block;
var m : message;
var i : int;

if (length(m0) = length(m1) && count + length(m0) <= q) {
m = b ? m0 : m1;
c = make(length(m0)+1,bs0_l);
i = 0;
c = c <~ (i, {0,1}^l);
while (i < length(m0)) {
p = (c ~>i) ^^ (m~>i);
ci = BC(p);
i = i + 1;
c = c <~ (i, ci);
}
count = count + length(m0);
} else {
c = make(0,bs0_l);
}
return c;
}

abs A = A {LR}

fun B () : bool = {
var b' : bool;
b = {0,1};
count = 0;
b' = A ();
return b = b';
}

fun Main () : bool = {
var d : bool;
K = {0,1}^k;
d = B ();
return d;
}
}.

game PRF1 = PRF0
var L : (block,block) map

where BC = {
if (!in_dom(bl,L)) { L[bl] = {0,1}^l;}
return L[bl];
}

and Main = {
var d : bool;
L = empty_map;
d = B ();
return d;
}.

equiv CPA_PRF0_LR : CPA.LR ~ PRF0.LR : ={m0,m1,K,b,count} ==> ={res,K,b,count}.
proof.
if;[ | trivial].
inline Enc;wp.
while : ={m,c,i} && Ke{1} = K{2} && length(m{1}) = length(m0{2}).
inline BC;trivial.
derandomize;trivial.
save.

equiv CPA_PRF0 : CPA.Main ~ PRF0.Main : true ==> ={res}.
proof.
inline B, KG;wp.
call (={K,b,count}) using CPA_PRF0_LR.
trivial.
save.

claim Pr_CPA_PRF0 : CPA.Main[res] = PRF0.Main[res]
using CPA_PRF0.

claim claim1 :
| CPA.Main[res] - 1%r/2%r | <=
| PRF0.Main[res] - PRF1.Main[res] | + | PRF1.Main[res] - 1%r/2%r |.

unset Pr_CPA_PRF0.

game G1 = PRF1
var bad : bool

where LR = {
var c : cipher;
var p,ci : block;
var m : message;
var i : int;

if (length(m0) = length(m1) && count + length(m0) <= q) {
m = b ? m0 : m1;
c = make(length(m0)+1,bs0_l);
i = 0;
ci = {0,1}^l;
c = c <~ (i, ci);
while (i < length(m0)) {
p = (c ~>i) ^^ (m~>i);
ci = {0,1}^l;
if (in_dom(p,L)) { bad = true; ci = L[p]; }
else { L[p] = ci;}
i = i + 1;
c = c <~ (i, ci);
}
count = count + length(m0);
} else {
c = make(0,bs0_l);
}
return c;
}
and Main = {
var d : bool;
bad = false;
L = empty_map;
d = B ();
return d;
}.

equiv PRF1_G1_LR : PRF1.LR ~ G1.LR : ={m0,m1,b,count,L} ==> ={res,b,count,L}.
proof.
if; [wp | trivial].
while: ={m0,m,c,i,L}.
inline BC; derandomize; trivial.
derandomize; trivial.
save.

equiv PRF1_G1 : PRF1.Main ~ G1.Main : true ==> ={res}
by auto (={b,count,L}).

claim PR_PRF1_G1 : PRF1.Main[res] = G1.Main[res]
using PRF1_G1.


game G2 = {
var b, bad : bool
var count : int
var S : block list

fun LR(m0,m1:message) : cipher = {
var c : cipher;
var p,ci : block;
var m : message;
var i : int;

if (length(m0) = length(m1) && count + length(m0) <= q) {
m = b ? m0 : m1;
c = make(length(m0)+1,bs0_l);
i = 0;
ci = {0,1}^l;
c = c <~ (i, ci);
while (i < length(m0)) {
p = (c ~>i) ^^ (m~>i);
if (mem(p,S)) { bad = true; }
S = p :: S;
ci = {0,1}^l;
i = i + 1;
c = c <~ (i, ci);
}
count = count + length(m0);
} else {
c = make(0,bs0_l);
}
return c;
}

abs A = A {LR}

fun Main () : bool = {
var b': bool;
bad = false;
S = [];
b = {0,1};
count = 0;
b' = A ();
return b = b';
}
}.

equiv G1_G2_LR : G1.LR ~ G2.LR :
!bad{1} && ={m0,m1,bad,count,b} &&
forall (p:block), in_dom(p,L{1}) <=> mem(p,S{2})
==>
={bad} &&
(!bad{1} =>
={res,count,b} &&
forall (p:block), in_dom(p,L{1}) <=> mem(p,S{2})).
proof.
if; [wp | trivial].
while: ={i,m0,m,bad} && (!bad{1} => ={c} &&
forall (p:block), in_dom(p,L{1}) <=> mem(p,S{2})).
swap{2} 4 -2; trivial.
derandomize; trivial.
save.

equiv G1_G2 : G1.Main ~ G2.Main : true ==> ={bad} && (!bad{1} => ={res})
by auto upto (bad) with
(={count,b} && forall (p:block), in_dom(p,L{1}) <=> mem(p,S{2}))
using G1_G2_LR.

claim Pr_G1_G2 : | G1.Main[res] - G2.Main[res] | <= G2.Main[bad]
using G1_G2.


game G2' = G2
remove S, bad

where LR = {
var c : cipher;
var ci : block;
var i : int;

if (length(m0) = length(m1) && count + length(m0) <= q) {
c = make(length(m0)+1,bs0_l);
i = 0;
ci = {0,1}^l;
c = c <~ (i, ci);
while (i < length(m0)) {
ci = {0,1}^l;
i = i + 1;
c = c <~ (i, ci);
}
count = count + length(m0);
} else {
c = make(0,bs0_l);
}
return c;
}

and Main = {
var b': bool;
count = 0;
b' = A ();
b = {0,1};
return b = b';
}.

equiv G2_G2'_LR : G2.LR ~ G2'.LR : ={m0,m1,count} ==> ={res,count}.
proof.
if; [ wp | trivial].
while: ={m0,i,c}; trivial.
save.

equiv G2_G2' : G2.Main ~ G2'.Main : true ==> ={res,count}
by auto (={count}).

claim Pr_G2_G2' : G2.Main[res] = G2'.Main[res]
using G2_G2'.

claim Pr_G2'_aux : G2'.Main[res] <= 1%r/2%r
compute.

claim Pr_G2' : G2'.Main[res] = 1%r/2%r
admit.

claim claim2 :
| CPA.Main[res] - 1%r/2%r | <=
| PRF0.Main[res] - PRF1.Main[res] | + G2.Main[bad].

unset Pr_G2'_aux, Pr_G2', G2_G2', PRF1_G1, claim1.

game G3 = {
var b, bad : bool
var count : int
var S : block list

fun sample_p () : block = {
var p:block;
if (length(S) < q) {
p = {0,1}^l;
if (mem(p,S)) { bad = true; }
S = p :: S;
} else {
p = bs0_l;
}
return p;
}

fun LR (m0, m1 : message) : cipher = {
var c : cipher;
var p,ci : block;
var m : message;
var i : int;
if (length(m0) = length(m1) && count + length(m0) <= q) {
m = b ? m0 : m1;
c = make(length(m0)+1,bs0_l);
i = 0;

while (i < length(m0)) {
p = sample_p();
ci = (p) ^^ (m~>i);
c = c <~ (i, ci);
i = i + 1;
}
ci = {0,1}^l;
c = c <~ (length(m0), ci);
count = count + length(m0);
} else {
c = make(0,bs0_l);
}
return c;
}

abs A = A{LR}

fun Main () : bool = {
var b' : bool;
bad = false;
S = [];
b = {0,1};
count = 0;
b' = A ();
return b = b';
}
}.


equiv G2_G3_LR : G2.LR ~ G3.LR :
(={count,bad,S,b} && length(S{2}) = count{2} && count{2} <= q).
proof.
if;[ wp | trivial].
case : (length(m0) = 0).
condf{1} last;condf{2} at 4;trivial.
splitw{1} last : (i < length(m0) - 1).
condt{2} at 4;[ trivial | ].
app 5 7 (={m,m0,m1,count,c,b} &&
0 <= i{1} && i{1} < length(m0{1}) &&
length(S{2}) = count{2} + i{2} &&
count{2} + length (m0{2}) <= q &&
i{2} = i{1} + 1 &&
length(c{1}) = length(m0{1}) + 1 &&
let p' = ((c ~> i) ^^ (m ~> i)){1} in
S{2} = p' :: S{1} &&
(bad{2} <=> bad{1} || mem(p',S{1}))).
inline sample_p.
condt{2} at 4;[trivial | ].
wp;rnd (p_0 ^^ ((m~>i){2}));trivial.
while>> : (={c} &&
0 <= i{1} && i{1} <= length(m0{1}) - 1 &&
length(S{2}) = count{2} + i{2} &&
i{2} = i{1} + 1 &&
length(c{1}) = length(m0{1}) + 1 &&
let p' = ((c ~> i) ^^ (m ~> i)){1} in
S{2} = p' :: S{1} &&
(bad{2} <=> bad{1} || mem(p',S{1}))).
inline sample_p.
condt{2}; wp.
rnd (p_0 ^^ (m~>i){2});trivial.
condt{1}; condf{1} last; trivial.
save.

equiv G2_G3 : G2.Main ~ G3.Main : true ==> ={bad} && length(S{2}) <= q
by auto (={bad,S,b,count} && length(S{2}) = count{2} && count{2} <= q).

claim Pr_G2_G3 : G2.Main[bad] = G3.Main[bad && length(S) <= q]
using G2_G3.

claim Pr_bad : G3.Main[bad && length(S) <= q] <= q%r * (q%r / (2^l)%r)
compute 2 bad, length(S).

claim Conclusion :
| CPA.Main[res] - 1%r/2%r | <=
| PRF0.Main[res] - PRF1.Main[res] | + q%r*q%r / (2^l)%r.
23-07-2013, 12:57 door TD-er
Ik zat onlangs aan iets soortgelijks te denken, met als enige verschil dat ik niet dacht aan de random-nummergenerator, maar aan de AES-instructie die op moderne (Intel) processoren zit.
Deze instructie weet de AES-encryptie van bijvoorbeeld een Truecrypt volume dusdanig veel te versnellen dat het zeer aanlokkelijk is om deze te gebruiken.
Echter zou het theoretisch mogelijk zijn om de meest gebruikte sleutel daarvan in de processor op te slaan, zodat deze dan uit te lezen zou kunnen zijn met wat minder openbaar gedocumenteerde instructies uit te lezen is?
Dat zou allicht het decrypten van in beslag genomen schijven wat kunnen vereenvoudigen.
23-07-2013, 13:29 door Anoniem
Door TD-er: Ik zat onlangs aan iets soortgelijks te denken, met als enige verschil dat ik niet dacht aan de random-nummergenerator, maar aan de AES-instructie die op moderne (Intel) processoren zit.
Deze instructie weet de AES-encryptie van bijvoorbeeld een Truecrypt volume dusdanig veel te versnellen dat het zeer aanlokkelijk is om deze te gebruiken.
Echter zou het theoretisch mogelijk zijn om de meest gebruikte sleutel daarvan in de processor op te slaan, zodat deze dan uit te lezen zou kunnen zijn met wat minder openbaar gedocumenteerde instructies uit te lezen is?
Dat zou allicht het decrypten van in beslag genomen schijven wat kunnen vereenvoudigen.

Misschien. Ik weet niet of de processor zelf non-volatile writable geheugen heeft. Het is wel mogelijk om de CPU te patchen (micro code updates), waarmee processor bugs opgelost of omzeild worden. Het bios kan zo'n microcode patch installeren. Maar of dat permanent op de CPU is, of bij elke boot geladen wordt weet ik niet.

Zo'n sleutel in bios flash laten schrijven lijkt me minder waarschijnlijk. Dit soort dingen zul je *heel* geheim willen houden, en als naast een klein (?) aantal cpu designers , hun management lijn dan ook nog een berg bios vendors in het complot moeten zitten wordt geheim houden wel erg lastig.

Verder denk ik dat de AES instructie voor (veel) meer dan truecrypt gebruikt zal worden. In aantal aanroepen verwacht ik dat SSL erg vaak langskomt.
23-07-2013, 14:07 door [Account Verwijderd]
[Verwijderd]
23-07-2013, 15:26 door TD-er
Door Anoniem:
Door TD-er: Ik zat onlangs aan iets soortgelijks te denken, met als enige verschil dat ik niet dacht aan de random-nummergenerator, maar aan de AES-instructie die op moderne (Intel) processoren zit.
Deze instructie weet de AES-encryptie van bijvoorbeeld een Truecrypt volume dusdanig veel te versnellen dat het zeer aanlokkelijk is om deze te gebruiken.
Echter zou het theoretisch mogelijk zijn om de meest gebruikte sleutel daarvan in de processor op te slaan, zodat deze dan uit te lezen zou kunnen zijn met wat minder openbaar gedocumenteerde instructies uit te lezen is?
Dat zou allicht het decrypten van in beslag genomen schijven wat kunnen vereenvoudigen.

Misschien. Ik weet niet of de processor zelf non-volatile writable geheugen heeft. Het is wel mogelijk om de CPU te patchen (micro code updates), waarmee processor bugs opgelost of omzeild worden. Het bios kan zo'n microcode patch installeren. Maar of dat permanent op de CPU is, of bij elke boot geladen wordt weet ik niet.

Zo'n sleutel in bios flash laten schrijven lijkt me minder waarschijnlijk. Dit soort dingen zul je *heel* geheim willen houden, en als naast een klein (?) aantal cpu designers , hun management lijn dan ook nog een berg bios vendors in het complot moeten zitten wordt geheim houden wel erg lastig.

Verder denk ik dat de AES instructie voor (veel) meer dan truecrypt gebruikt zal worden. In aantal aanroepen verwacht ik dat SSL erg vaak langskomt.
Je hebt nog een TPM-chip in je systeem zitten tegenwoordig.
Deze is bedoeld om sleutels in op te slaan, al is het oorspronkelijk bedoeld voor de content-industrie. De vraag is nu of de NSA zich daar ook toe rekent ;)

En als antwoord op een andere "Anoniem":
"Waarom is Linus hier eigenlijk zo fel over, is hij omgekocht door de inlichtingendiensten?"
Ik denk dat die felheid eerder komt door Linus' ongeremde subtiliteit, die hij wel vaker ten toon spreid.
Volgens mij is hij absoluut geen makkelijk persoon om mee samen te werken.
23-07-2013, 20:13 door Anoniem
Door Stoeprand:
Echter zal deze generator vrijwel altijd op de standaard manier gebruikt worden. En dan is het gewoon een pseudo-random generator.
Wat ik uit de cryptografie weet is dat volstrekt ad random cijfers genereren lang niet zo eenvoudig is als wel wordt beweerd. Er is wel software op internet te vinden om de getallen zo goed mogelijk ad random te krijgen, maar wie garandeert mij nu dat Intel zulke processoren levert dat RdRand goed werkt? (zie quote).

Ik ben het daarom eens met de kritiek dat het vertrouwen op dit moment tot een dieptepunt is gedaald. Ik heb het daarom ook helemaal gehad met closed-source.

Check update eigen systemen.
De Intel processors in mijn beide computersystemen zijn (codenaam): Sandy Bridge en Arrandale. Ivy Bridge is dus niet aanwezig. Je kunt dit natrekken via het progje Speccy via de website van Periform.

http://www.piriform.com/blog/2013/6/18/speccy-v122

Features die in een bepaalde architectuur geïntroduceerd werden, blijven meestal heel lang aanwezig , ook in nieuwere releases.
Je moet heel diep in Intel zitten om 'meteen' te weten dat Sandy Bridge ouder is dan Ivy bridge, en *daarom* iets wat vanaf Ivy Bridge aanwezig is niet zal hebben.
Maar heb je Haswell, dan kun je er vrij zeker van zijn dat je ook de hardware rng feature in de CPU hebt. (want Haswell is de opvolger van Ivy Bridge).
Arrandale is ook ouder, heeft de Westmere micro achitectuur (mobile ) met geïntegreerde graphics. (opvolger is Sandy Bridge)

Anyway, voor jouw wens moet je dus zoeken naar 'NOT rdrand support' , niet naar "NOT Ivy Bridge"
23-07-2013, 20:29 door Anoniem
Door Anoniem: Voor de liefhebbers, bijgaand een bewijs dat wanneer de INTEL DRNG op de standaard manier gebruikt wordt, deze
rekenkundig veilig is van complexiteitklasse IND-CPA. Deze generator kan echter wel op een andere manier gebruikt worden, zodat je de True Randomness eruit kunt halen. Hoe je dit kunt doen staat beschreven in paragraaf 4.4 van de manual. Echter zal deze generator vrijwel altijd op de standaard manier gebruikt worden. En dan is het gewoon een pseudo-random generator.

Bijlage: Pseudo-randomness IND-CPA bewijs van de Intel DRNG

[knip]

Dit heeft de smaak van een beetje showen ....

Met wat zoekwerk lijkt dit een bewijs te zijn met hulp van Easycrypt, een tool voor formele bewijzen van security protocollen.
http://www.easycrypt.info/

Ik zit niet goed genoeg in dit gebied om het goed te kunnen lezen , dus een beetje uitleg van poster zou (voor vrijwel iedere lezer hier) dan wel nuttig zijn.

Wat ik weet/zie en vond van deze bewijzen is dat het laat zien dat een bepaalde constructie gebouwd met elementen met bepaalde eigenschappen voldoen aan bepaalde eisen.
Bijvoorbeeld dat een aanvaller met zekere mogelijkheden niet beter dan kans <x> kan voorspellen wat een volgende of vorige bit is.

IND-CPA is een gekozen plaintext aanvaller , die een polynomiaal beperkt aantal berekeningen kan doen .


[knip source]
23-07-2013, 23:32 door TD-er
Door Anoniem: [...]

Features die in een bepaalde architectuur geïntroduceerd werden, blijven meestal heel lang aanwezig , ook in nieuwere releases.
Je moet heel diep in Intel zitten om 'meteen' te weten dat Sandy Bridge ouder is dan Ivy bridge, en *daarom* iets wat vanaf Ivy Bridge aanwezig is niet zal hebben.
Maar heb je Haswell, dan kun je er vrij zeker van zijn dat je ook de hardware rng feature in de CPU hebt. (want Haswell is de opvolger van Ivy Bridge).
Arrandale is ook ouder, heeft de Westmere micro achitectuur (mobile ) met geïntegreerde graphics. (opvolger is Sandy Bridge)

Anyway, voor jouw wens moet je dus zoeken naar 'NOT rdrand support' , niet naar "NOT Ivy Bridge"
Je kunt ook op ark.intel.com je CPU opzoeken en kijken naar "Intel® Secure Key" vrijwel onderaan in de lijst van "Advanced Technologies"
Bijvoorbeeld een van de nieuwste i7 CPUs: http://ark.intel.com/products/75125/Intel-Core-i7-4770T-Processor-8M-Cache-up-to-3_70-GHz
Bepaalde advanced features zitten namelijk niet in de budget versies van bepaalde families. Generatie van een CPU geeft dus geen garantie.
27-07-2013, 10:42 door Didier Stevens
The CPUID instruction can be used to check whether the CPU supports the RDRAND instruction. If yes, the bit 40 of the ECX register is set after calling CPUID standard function 01H.
https://en.wikipedia.org/wiki/RdRand

En hier hoe je CPUID kan uitvoeren in verschillende programmeertalen en op verschillende platformen:
https://en.wikipedia.org/wiki/CPUID
27-07-2013, 15:12 door Anoniem
Als je de Intel DRNG Software Implementation Guide bestudeerd dan kan Intel de DRBG en de Conditioner decrypten, gegeven het feit dat Intel de decryption keys heeft (zoals verondersteld in het artikel en in de random.c routine in het commentaar te vinden).

Overigens geldt hetzelfde voor de procedure om de raw randomness te gebruiken in paragraaf 4.4 van deze guide, omdat de key van aes128k128d bekend en fixed is. Ook hier is de randomness te decrypten.

Met beide bovenstaande issues zul je dus rekening moeten houden in een entropy extractor om de raw randomness van de generator te extraheren.
01-08-2013, 11:13 door Anoniem
Op https://en.wikipedia.org/wiki/Randomness_extractor is een goede uitleg te vinden van post-processing functions voor true randomness extraction. Uit de documentatie in de Intel guide blijkt dat Intel voor de randomness extraction AES gebruikt. Het ligt veel meer voor de hand error-correction codes te gebruiken. Deze zijn gemakkelijker te implementeren en hebben een informatie-theoretisch bewijs voor de hoeveelheid randomness welke gegarandeerd is gegeven een bepaalde hoeveelheid randomness aan de input kant. Een error correction code als randomness extractor doet namelijk een lossy compression. AES is moeilijker in hardware te implementeren dan Error correction codes, doet geen compression en is omkeerbaar (als de key bekend is).

Gegeven het bovenstaande is het dus zeer aannemelijk dat Intel met het gebruik van AES als post-processing algorithme een dubbele agenda heeft, zoals bijvoorbeeld het kunnen decrypten van de randomness en daarmee het kunnen kraken van de beveiliging welke gebaseerd is op deze randomness. Dit is ook reeds op meerdere cryptografie forums verondersteld.
01-08-2013, 12:15 door Anoniem
In VIA processoren (welke Intel compatible zijn) zit ook een true random generator. De post-processing van deze processor kan uitgeschakeld worden, zodat de raw randomness getest kan worden. Ook zit in deze processor een Von-Neumann post-processor welke bewijsbare randomness opleverd.

De AES post-processing in de Intel DRNG is niet uit te schakelen. Ook wordt de true randomness geexpandeerd tot pseudo-randomness bij Intel.

Dat de raw randomness niet te testen is doordat de post-processing niet uit te schakelen valt geeft weinig vertrouwen in de Intel true randomness source.

Als je true randomness in een processor wilt gebruiken dan is een VIA processor sterk aan te raden om de bovenstaande redenen.
03-08-2013, 14:31 door Anoniem
Zeer interessant onderzoek van de auteur.

Ook de reacties zijn bijzonder informatief.

Ik vond op de link http://wuala.com/quantumrandomnessapplications nog een aantal toepassingen van True Randomness.

Dit toont opnieuw het belang van het gebruik van goede true randomness.
04-08-2013, 06:40 door Anoniem
Wellicht dat de link http://software.intel.com/en-us/blogs/2012/11/17/the-difference-between-rdrand-and-rdseed nog informatief is.

Volgens de beschrijving van Intel:

RDRAND: Cryptographically secure pseudorandom number generator

The numbers returned by RDRAND have ADDITIVE prediction resistance because they are the output of a pseurandom number generator.

RDSEED: Non-deterministic random bit generator

The numbers retuned by RDSEED have MULTIPLICATIVE prediction resistance. If you use two 64-bit samples with multiplicative prediction resistance to build a 128-bit value, you end up with a random number with 128 bits of prediction resistance (2128 * 2128 = 2256).

Dit is een van de verschillen tussen non-deterministische true random generatoren en deterministische pseudo-random generatoren.

NB. RDSEED wordt op dit moment NIET ondersteund door Intel Processoren maar wel door VIA processoren !
07-08-2013, 00:22 door Anoniem
Een randomgenerator op basis van verval van radioactieve isotopen lijkt me toch net iets veiliger dan op basis van een of andere blackbox van Intel! Sneeuw op een analoog TV toestel of ruis van een FM radio lijkt me ook wel ok. En zo zijn er legio oplossingen die echter nooit geimplementeerd zijn geworden, dat mag niet!
19-08-2013, 02:25 door Anoniem
Natuurlijk mag dat wel, maar een analoge TV-kaart of FM-radio behoren niet echt tot de standaarduitrusting van een computer. Ook een radioactief doosje (rookdetectoren op dat principe mogen inmiddels niet meer) is niet echt handig.

In software de entropie van een toevalsgetal verhogen, lijkt me een goede oplossing.
Reageren

Deze posting is gelocked. Reageren is niet meer mogelijk.