How to accurately calculate Unicity Distance for English? The Unicity Distance for the DES cipher is around $8.6$ characters, and can be calculated using the $U=H(k)/D$ formula, where $D = R - r$, and where $R = 8$ is the number of bits in a byte (ASCII is 7 but we are rounding up), $r \approx 1.5$ bits is the average entropy of a single letter in written English, and $H(k) = 56$ bits is the DES key length.

If the above is correct then, for a 16 bit cipher, your UD would be around 2.46. Surely you need more than 2 characters to tell whether what you are getting is valid English. Can anyone explain?

This is a follow up question from here: https://crypto.stackexchange.com/a/22929
The code to run the experiment can be found here: https://github.com/coolfeature/sac

Here are some calculations:

Unicity Distance is The Entropy of the key space / the redundancy
D = R - r
Assuming R is 8.0 bits (ASCII) and r is 1.5.
H(K) / D == 16 / 6.5 == 2.461538

We need 2.461538 letters to get a meaningful message.

65536 candidate keys - block size 1 (2 chars) possible meaningful : 8 - chance of getting a meaningful msg: 0.000122

2809 candidate keys - block size 2 (4 chars) possible meaningful : 64 - chance of getting a meaningful msg: 0.000000

1600 candidate keys - block size 3 (6 chars) possible meaningful : 512 - chance of getting a meaningful msg: 0.000000

896 candidate keys - block size 4 (8 chars) possible meaningful : 4096 - chance of getting a meaningful msg: 0.000000

20 candidate keys - block size 5 (10 chars) possible meaningful : 32768 - chance of getting a meaningful msg: 0.000000

20 candidate keys - block size 6 (12 chars) possible meaningful : 262144 - chance of getting a meaningful msg: 0.000000

1 candidate keys - block size 7 (14 chars) possible meaningful : 2097152 - chance of getting a meaningful msg: 0.000000

The key 0x431a(17178) found after 7 attempts
7 blocks (14 characters/bytes needed) - DECRYPTING...
Message Entropy = 3.854248670673993

A 16-bit cipher has $2^{16} = 65{,}536$ possible keys.  Thus, if you try to decrypt your ciphertext with every possible key, that's how many different (and essentially random) plaintexts you'll get.

Your calculation suggests that $\lceil2.46\rceil = 3$ bytes of ciphertext should be enough to uniquely identify the correct key, assuming that the plaintext ordinary is English text.  Such a short ciphertext would normally be characteristic of a stream cipher (or a block cipher in a streaming mode like CTR or OFB), in which case we can assume that each ciphertext decrypts to 3 bytes of plaintext (which, for an incorrect key, will be effectively random).

So let's test it.

I just wrote a simple program to generate 65,536 random 3-byte strings.  Out of those strings, all but 3,399 contained bytes outside the printable ASCII range, so I filtered those out.  Here are all the remaining ones:

F\G %EZ Cv> N}Q W&l LS} mM` "'8 Zi+ {KB '`j a6@ ;7O 3Hc }fH }&d W@L )]v 9Qy r1Y
ZG2 dc} `'x @4? WiC #7J T3' dq: s&. is_ laK Xr! fPi "MD LS4 (oz ELS 5${ ?6" E@,
PJ= S;C u|G :ap 1V~ ?Or g2V uE4 (O7 O3J bQ# a:0 k\: ~"" rWf eW4 Iqg bdT Oe) DYU
]n% A\V LzT s/N 1JO lZF *SQ p}/ YNY -V9 3f< r?g *Kp yyp E~Q <Jk r'w <^K c+_ w*w
iRt 8z, Fyf nq` K+. DuZ O<D 3co -Hz t?" !$S s`! ;wT }-M ZJI C9Z v8a *,D QcX 'cq
iM) $YX IDy K}9 Zmm J!y z[@ dXl $TC bR5 YDF 9/G $-p Pzu  Ff wpI {d" ~%# 'xw hpg
'[h E\7 Qsp ur# YN" TZm -}0 W(` T$r ~.J tKK ?~m \Y8 30] *P^ YlH g R # 4 nhs $ts
HS5 _i5 /2= al- w.t T+, ECg bU: Z}V w?6 #z  `R) ]n{ AiH jw> ;f1 (#Q  `S H_; a_O
n){ [Mt &"D xn  cr6 hJ~ HA2 ,gb ^/H 2M! &cZ }9K +wg Ivn {b{ ci= O7L %N, pac )|+
)n[ ivn td2 ^S} $Rf }[p %n% yWg F+V y-h F.6 36w D(A M-h Bea (yt Ka| w?b n)L z7W
8:d .l\ `|E f*" 8N% :_N $:p Z w K"l &hV Pr_ n/u $d- g   3L] g%y C|% S>P O[{ #IV
g"6 >tA Jp| Q={ jaM Q7U !#X pv" <JL t6= JIl %,` .K\ M,6 "MV kPH rMH ^T* .Hd jST
yX[ (~p GX} pSx S}?  @A }f_ Hy, ja1 cnp '5- zuy (\] u6w 2R% v([ QBK /jR ewr X)i
Z[: .F{ $]( {IS V4J ?01 K@+ 2VW |Ci -M* eb. oA8 1," h^s 2Dx V>F ndh 5VA `]  u(l
6R. -G~ s,b !Rd O]E [%o xBg wfd ;`^ L0' )<j y)M VO= /I* unB 3Ib VDi ~ok WBm BL-
u[9 1P6 @#d G=w %V/ YA> 'CT P}@ *E` *4H :$z /o$ w_J iBC lG| x}^ m7^ ]4v vz\ }-@
TE- XV{ ,6# p7G IvG tID 2g! >N^ x^" :^[ EG. 6a1 "D$ {YG QNS w}o +.f ~F- "kc i){
bq0 .I_ \gX 5wH .RQ 46U ]:+ sGx xOX 2<D ozM `|< k+: }$I ].B m%: Z1! K&^ k]] 4l2
`aW .q? 'K& zwp kcA O]p l@B (fg kJd v ^ k*> q:} q1f `_$ iz. ?b( O\H ~Cp )~' BMW
rnx \ms ]cy X!G Fs' zg1 px` 'v4 'V= jn1 ,"_ E+` ==, 2^T s77 <Ji "py uni 0~v 5lo
(Nd BL< ]V0 u"' r[= 6T\ oQW [pR cIN ~w5 |uT .&H QO8 itz g'E "Ea q}G h8" xH8 .%\
g^F Hh: #$b vg$ }+* #hz }TH v!T .~> 2=f QFs c;M 7SM "i| .3V VH4 {5Y ^b_ {q% w%/
QJ+ !u: m>> 7&g _`U Dwh 'OI :uC a!- !go f;1 3 m QqV !&. Xg> Dg` 71p UnJ 0Vc TLO
F\2 %(P w/G aJC SO8 ,k[ h#e 4r0 YG} PD2 |f^ #Q* ',L L-2 W"# ',n ukt ]`! qp! p6R
*`; il  Z!L uG+ S"" bJ$ kpX jRM kWM c4% z{8 0]! ^UK s^M ,$1 .TX +r! .D? U<+ Yr$
-i` 8-- .sg d&: zIZ sD| cVy :`U I"& n]u t;8 h4c lX} E P :9d J # LQX AdG VLP f8^
2rj hsg Slu o=G G"^ CEu %9) 'l4 i6P L$~ \jo hNl {l8 /RO 53V W}w .:O #Ov M'* 6yx
olv j[: XmZ Uus OUK hQN <mZ 0(& 6T5 _<e `w> $Ym F+> )!& j~8 _I* <t# VL~ L:M -t
:`r r9^ A<F 'L; z1g nzG :&= wp) KNk Z5f i)D @pC z-] m=  -j4 mN? qC) l5[ 31w ^,Q
1FZ w<T r!N R?} PaC edN Owa '^> }>; zju !XE ,h4 Ugx [=Y _vx "qf czs zM, M$e OW]
0o. X]` zT` /Fb k~} TVb z2B 0?c W{< *?g mpg llL .)8 ;1S '8j UO| ~a_ soU z+Q Q,e
L # ]Jn !jZ .,# M6{ Qyj m(| vPF  MY Z-5 :]^ Pt2 k[+ mYO W&D `"; <bF ]ZQ L?9 (-}
aE: yz1 9b) .pK t5= sDq eVx ?kL n*/ =B< (gl gv" lB/ ]o8 RQ6 r~_ DWN tY> q2Q 3-U
QeZ .Xx "]f B]3 xjS ]V9 E+c (Kp X.: wiD J9A m'Y _4j |}L SPL 3k, G4I zHn 3u6 `I'
Ka# D5. eaI 1p| t.Y ]"E zA; 81w Qzg !hK W@" FI( T7[ d9' Hp; BXa u@d &=[ b'8 'B&
:aF m.C zjs A)| Oxt ,so 37H 6VM P|/ /|U 9Q, lnn s%' |l0 {Xs q|F q ( 0)v p`z ):S
dZ. @;t ]Jn JVc .CD !+& #Vg %6Z VOl QoK ;z3 9A: m_X ",4 TQ  #}L  }J :O[ GPg $y<
|k: &f) (Ak Mx, N\L "bC 3}A +rL :<= .(I L?x D&] {Hr Np1 n*} 3n{ B<B Ub> edE F5@
I@_ Tv[ 4#9 j)J Na9 F}b 9T/ H#b .<Q WGC yQ+ ,oJ [Q% (rh 6C9 zw~ 9PS 0EG n$f o#
:.l 1!l 9}J b<2 fh% ^nb x<_ h9< DRO ed/ V>Y FlN 5zL 'H_ ssN pNL k'E |hR A~a ?98
s7G _4v a42 !zc zmg Bp| (A^ 6*_ rAv SES 'x= T*R <PY anf |pd #{g J%* ,2) <}? *1G
wi< T)q yq# +_z B'> s.> f|R GOY $Zo xEi M!a tHB 1Q  16* |im ./! 3W< zKl k+' q?o
&h- ^[" wu. O3I sU] 1.Q k+/ I*h -<; "V/ +R8 5&c ,>e 9p0 4zU NUG 2{b ity qz^ Y@0
q%] Kmj <@! $Cm wn| ?m] Ug} 'TE +{' Esj L<Y 7;t d39 ^Z3 R6J DCl ORt ME\ 3JU [Jh
TqK Ys  0{/ `ZN zOL fd% $'y |wp CJ] Y:L kp8 XV4 t+x n(g U`$ AcT eCJ fQX `3p n9R
[k; .;A c(c khd >P7 A~2 6xr ->_ $:Y |g% iwv ZC@ -'" Q"_ ("+ nGT 4px rAQ p,. \tb
Fyv QzQ >u? ]NM 'o@ 9N$ :lQ GwW OSN u_> Ixi ~Fs qB) 2C+ +IJ [X- ,)t  "Z <cV ',T
K>e Gl6 R[< y_" ?Q\ ;jL F`H ?mb `j7 f!M ~#Z BA7 ENP e'+ `Jx ]** HA> sJb Dh, na/
(~A K0Y 8>m X?t b'j }0I R!P og. c{V  if _Q( D/E Ph> v0  8Ui P/@ )3/ yhT lrk >*F
j]  vaL wRz xK& 0yk =+f |W! Q]L R7U Zqz 6iT  ?- " 7 v#8 /\~ gR` `+h C:, `;T jIo
IpB 0oz YH@ f&: ou^ Rp} k8@ rJZ yw- i|{ Jr{ %Ak 1,\ OLh P[n e&@ !.P GRY y?d /me
)od -xU f4= (X= :0S [Kj 5,V w`S KCA v2j VOC D#g &3t 'r7 bcW V'd p!r %E7 KG` e\5
c_Q vJ  Lym up" 2e% aC} :Sp "PO  br i1% jno W+G !~! [-2 {N$ M)r GPl 7|r :R^ 5f*
1i= Dew {?b )>g |8{ tA@ /Or _#Q #0Q %%G HN? |W[ *)] %fr InF QPJ k:> ]At y<. n>v
~6L ]z< qPt KJM tx> ;)} 5cF J\w 0z> y!M ahV (Js ^ow V[5 LuV {"4 o?) >[$ C@  Ri|
b{N r4s U92 E)s {!7 h)7 1t( Hp! /iM W$2 q"s tFx ?)5 '6u t_; f*D 2=~ &5k Ok7 9MY
cWO SHs dC> >6( @L- F57 t:& v0y X=j PG{ ?#[ {Lz aEO }~I \t! Z<+ lAy mHf 2AP ~:_
eb# [ko mO? 2|U ND1 8Wv @'0 |B$ OX} 6)q `z. H{& 7Y7 o2Q Vu. 2M# [NB &(W 39[ fb$
9u? L<w _G  l-Z 1Pt rGt Hnq ^y^ + $ 1R% q\W 8{Y aq5 4\] W\O 3Yc `c% x.P MV. +B/
y&0 @bZ Zu6 4d( \tX gUq #/] b30 XI[ |?3 #>2 qQC 'x4 (>' x.W %A< i/3  kd '~z |Dm
pc' S|P O[' u07 */1 zO{ />c %(N 7<X 8r8 <6e #(R GyR %}V l(6 /PA #/6 U#8 N+\ 6tS
sJ| {[e VK_ @[p bmV %[, q,% m4U IHQ 0O> *88 h36 !1, C"I zWU b-d -SL ?m! Uym CbI
8dm (|b [I, 6M5 3{L -T2 =?S =p8 /9; _)b  WC 9uQ 7h( zU% E*J #{0  e" OH1 BWf zQD
9}L I1? UTT hvU ,uB Y22 r;% K.j "}u 2Lt @)2 OOX !3e "E| *c8 )!9 6l* ,Cw -Lb h5V
/60 :!  5YP J*/ a/} {.7 2*4 po5 Ea$ hGd 8nH u"| Ls+ |*Z -he A_y /b* 2%> ]lv MC_
Cf| E8{ w,0 3@v kXp jrj !{! 3@E Buk 6&2 )J5 +~f fBO 4SD _F| yU" @uW V[Q T1@ ]Ax
YMg tcQ +|c nHG S!z (g> _*K W;M .AN }w$ hIQ @EG SeO fH; yZa uGx 5;^ >F_ eET `(?
!lH ;Gn ^Fn BWC MZf #!h vjj p'o /`i J*; #.F l`t |wf :U@ MO6 G`O j1/ \v+ ;!{ H]{
g'2 kc0 Y]u =aL g<0 (4z zMl !ov ]v: [p6 mr| 9TT g\= XVZ Hiz TAl +*f X2N kuS ^%M
^/M *|0 188 "cU eBH 6!| [|( *9g 0bu .M* o][ %m` ~9e exz   s sX6 JX" 8\R )}P /^K
U(` fwV 8wJ 45H 9QM /K) z%V j4v (^9 zRx j9y cI% mf^ JEa 1,[ J00 \_{ iSF Rj3 zn*
0C  0r: p k _]j 9<A =Xx \UD ^PR ^bV }YZ hXJ "S% Urk _y8 kwh GJ6 pr< gws [7" qvJ
pRB 1/| -U# $1^ uSJ l<; +mQ HJ| aMG TF\ `"' :Kt dR{ 3Zc LiU [CY bP1 GPX %|_ 0bH
l6? &+b dQ2 gFO Iw< RY% iVp A>g Fm( ;,J JEQ @<* p64 P}( +h_ V(4 +/? 7cQ GQ. 8{_
\s3 ?z9 ~aP B-2 <vg  lk h~v `:T #>m 9Sy iyc M8/ \Te g>\ ;.1 &c7 W_V VCZ x[0 66g
g3= cI{ R_, m3s &x$ Am' ==3 r)c NHG |)H !~O C4) L.> 7Kv bO< R!> DZ0 62o 'tO  ?%
g4o T_t @Zj tBi [,t u:V N}* qDX Wz< ;e> d$* X|F m?/ Xp( %0] uP5 (u2 qi! y`\ B[\
-{6 H]C 9:| (P5 EUu u)a (%+ N<B 5jF rL& 00e -'c I g !3  FCg I[R `%\ aGI 8Vy {oD
nTX F@t $RV ge5 E6e L!% V~  Qno =f' 5$m kgk  l7 %CB Z3T 2v` 5[" x`l 5@- dmx oXT
six EXh TK^ dz@ %mw zo] *@U 91F ?c) Oni OZ{ drv *EC 9l\ "=? 5;* kB3 ?&z W0'  G\
q%j Cr_ ysl ?_O bp: IXv A3) <Y% M w 0&Q &oT Gdp Hj{ lvd *h6 w,W z~X kZ& B]Q %/"
;IS t$[ m0* UHL ~U4 uA& anv w_[ ijW qcV >z| U;$ JY\ #:. }N~ Rm+ Z2~ L:y vCg 1)i
AH{ YG8 s'+ c}# P!W `e` Wr+ ^1K r!6 ao{ Q%P j<# }Q= {+- _8] \U` D@o I`+ i)R JJv
6?V z?? fx# Z+z smc H!y ]4< :J| u2T _dK lvU }I3 &j@ ;;4 c|A D87 ,y] K[@ |.f ,?I
VS0 .dk q4' "RW vZg gvP o*b \#. uX~ ~#: BUY X%S Kuv <"? kMP gWR @X` tNZ 1l~ "tc
ZMb @*+ )/u ;eI L|y ;RS XFR VP' Z}s ?y9 F$  kEK &Hn qoA a`d ht? \.w [w4 Bv[ w)w
oc  }fl lo$ vUk p3R `(h ")i `LB 3z$ go% Wvz A;9 !!Q L#G  Pj  CC 58c qhI |FL &L1
CmL -#t M@p gkb H?P b6: i`- XSC @:5 e]m )4Z u#b <}Z 7NB >i? {@Z k"f Qm2 $YM k9a
`z5 .%4 $6$  JT NPC D<; swH tkf j>) ;}e &jF l{o k&+ h&K ,RN ]I" 4vT CUR 'gb dV/
fFH ('v k_Y LfA 2y; RDV j)B Ces kX" #]T |S= 6`8 h'a @w^ TG$ [g$ 4#6 'r7 KQX Z6b
3$I MXQ /l  ph& -F6  0] :k. j?' US3 =S} |v3 (A1 iv> 2a= x%h a)K C@8 4H^ `Wq (2z
)30 y9- Cur [>/ [V/ -}Q `Bh Nti pHx ?d? */1 j0> ]i2 +9W yw" Glq w6Q ?R' &db E2`
]F. $sc 0?w }/& }:P =~M 1Dz |rg ]uk l`U UIg V73 a~% 3fd kul |P$ (#d j>~ mwS jJv
kfS %?| e`Z (B3 f[t =e} fg^ 0^) ju{ P'X cgW lJk Bb4 v%\  #/ D$c uJQ yb4 Q V TLq
^"G fK| bY) br7 (.^ 7Ep 380 Y9n u<  dFv ~pm J;. Te[ g#3 +k| 'Dx oPS Wu/ %@F 1k?
eGo Aw" -m/ 0)A t39 l&M ^*^ En" N`2 ~tG q[v nN/ %3!  H0 +w@ c\a m4T E,- \+* *0.
VA] Ma% "cc 9W# m{f 1Vg ^I$ w 0 nyY ]h= Wc9 (9l ./0 "69 =8z !?$ qB+ $>j |1g EUo
x!5 j8G 7IL d4% l`M gk= vh: F4o W)E >o! qaB x/n l79 RLV YVC +|c D"$ 95j ZCH dD2
foC }T& #di ]~j OP} bCs n'J D/t <!\ \#" hP0 n51 (Xz 5es K&o RM1 !41 ~U[ nw5 &h'
>Z| +Lo 0f| Fe~ jF^ kuu A~B ZVx `$' V0P J@2 L1C dn% w@b ^Tj KM< uyc Q7d XLc 6K%
c~" %Z5 R,5 /~= nm: fN6 %Zs 5u+ xQC M`W (@- a$[ Ns; |_B 911 Kqg %PZ 8}* |>+ \]6
%gc ~*i ATZ E[x !M3 >ia wZ! War >t2 HDE ~Pd ]@j 11C |!0 i|G [@P ek& Iu. LNf 3~P
UrY uTA v=P MRc Rz] Wf, =0| hv0 o[/ 00R X/{ cL] xTg eI. <L7 }QO DS5 yg! 2\} _?|
AX` ;=1 m p b~! 4"y ?4T GIZ 5*e @]@ *,~ 1lY {0A >tl #V&  yZ xSr hr& r2B %TH aw8
EwR EUr w+U c{W H1t X,5 KlB r<$ a*^ AJJ i]_ '}! g%i $4: H#5 c`K ?W3 L&E ^%' &?/
iYq 6=& $1r "0f 0c9 5W% W`o %9~ BA2 TIV 4zY n[# )ZL Md\ aPf {ll s8Y LiB rjw yd.
H<p Gqn u_q uS4 >sD /&\ ^4[ L{N !=p 3E! N27 n?u BJ] ,*g m"W %_> hzY Xcd /1@ ^o^
|mw p38 $z, Sp* fzJ G#> YD@ +Mq C}s 3Sk svY a~; BrN -Nu $3{ V2> ^-. b[E IFk ?zX
eal X^\ 1#= m/[ *SU $8l K[W <Ms "G< 3=J Ps# !^b H(k ~pJ )5L iHp -Ss #KW 93Q $KZ
Lbf mfa il^ rb& -LW Q)* -6\ .m_ ,Yl Xqp ?-s X@B `jl F-\ &(% G|J Wxe 0`G ho2 G.7
Gkb T!9 qD} ZX, T,@ MS8 >EK WM( x!I #Z\ `0R x5> R 1 5O) g?A m?z 9 % g]o F/F ^B{
=qa X[L |rA X>w 3'F H1t 7@A SfJ OC% #?o ob/ Sxm ;Ed ?\^ IOe GY1 a2_ OW) 4Q. aS~
yD+ s3q )(v EOU 37= !N& (=9 ]Nj qJ< t#^ JEB Om` 1X% ^4m rL, I:8 b1+ k,' D|t N{u
Bn3 !$K 6}Q T'9 `^B CBD Bk: q:1 ,Mh ] C (_N *j* I+\ _"? }IR -hF 3;? )*[ G6o Ktn
=G4 ~!S UR; Al, :3Y ]BP PJ0 8rc [k, 8p8 z\V u}- )cP Z@8 6{+ Zox "Pe ;E* Mj: "Oz
*c5 qL* gIa H~s z'] #dy mNT Asb "m* zw: XXP  H( Vyq ii6 $Vi AOZ "u; 7c+ M<G X7q
5dH T)v OX( +t  'ac G$4 4JZ VJ) kxI Xww ^.E sa$ c<j Qc. ! X u[2 m9$ D2u f7e -"f
:?V yex +AN ~3W h8n .m" @>i LM+ qAk Tq3 w$+ 0Pz g+T ed  e#' a1s 6P% jy~ (V/ p-f
q G 7.\ Zdl yxg DI' |Au pY1 K=# #xu y73 rv; bs) Eo} m/% <a0 P8O 0]p 4n> jRz Hys
Dlx k2* ePU X,{ u$o gIx O1@ [dH yjh 8Bj t@^ uD| AHd =CT rCQ Pu9 J@e C.Y z<k *2F
$`j ^&z J2, cKg g}' d?. t;8 9T\ 6jZ ;v] 8am @-0 2"/ /GE *6  EPK hUa *cb T=b p~F
O&\ 6{k LO" l9: 25e SKS CKC gC; X9+ N.3 I~% ^Qs ,C, D_@ )xx 'G) wl4 KGq 6:X l9^
~^_ <nH sp$ f-t | z @i0 q>7 017 Yge BF*  +g 2d^ 1lU /Zr q"i c,J 4ys /UB Mk3 NSn
Lbg %,/ *'6 2sS 3t= 7(t C[A 9.x V*m P?m {Z9 4"U }_[ -mT \0~ S%, uu( 5=D ,Z/ OI<
fS+ C^) H"< Ki= $^9 OJ% Tav *Fe ,p1 n0" #Lh {<9 O=b r\* O\) +[M ?^x @o; FKs Jd}
ARc r+P : [ .AW $DC D*C ~i[ {sY q\p niX sv0 5tC x!w g4L MS[ \`@ uuq H`4 K": G~z
|R} o;< cP% P@N T@J &Z; dNu xLx /eB BIH e%] Hzy {1< F\( {!' _{[ kZ$ o&@ yAU J4C
k6  E>/ k?] E!w g~g u!> N6d vw% hp_ c)' /'w }*t ]H- dT6 067 S(/ a?. i=: tH? ,TE
B}\ K M 2ao qfd ~`@ +D@ Oqx eHG Px^  QA k4f *mR 0T\ $Fp ;ph /XZ M(1 5*b :Fd 5R5
a9@ .[s wZy >@4 @?S Qd1 K*S P]Y \ [ &I8 / 1 2PF mD- :"\ e9s ,Q) neb |0M M&k OKB
znw {h< wmU '~G ;S_ ;td ~}B a<{ +kB 8tS 0eS *tq 52T Q.j [QB (4M xI/ ~k- Z9M ^(V
fG^ 7'K _M1 94# pLo 9&/ p/j _'/ [ 4 GIF ~pi \/; JAz "6X n,A :/` %B9 E&s CCm 6j5
l`' GjY ,LH b"q zU[ wta QH8 W"H v{e usF 3qd lUK $aE KpF ]qm },> MDD y(9 _4< ]E^
Sd/ Xs5 }GD b30 >>3 (z. PW\ TQ) I|} I6D {5+ ; f ESA ,s< \`" W?Q cp| 5Mv /f+ 0/R
:k@ Y:e "R[ *uz [9~ KiT b_% &)e "uY S,G /`O m]C Y^h k6G yxo 2"' tpU Y?$ )ig 5h&
@r| a]L >hL $=N fAo >R| D=} a\: ]HH rC^ 1<z a_> k#j lA- a6Y lXW <X/ >UM *q> y}e
$o# ]]h [Tj #`i wyF }we k_$ <'I bor @o% UsX 7RL &NT .&+ 9D# /P. RQg akK <u  kp(
44o 8dq 3U( up% ur6 ^NP 9I- soH 5j@ 3-O :|; }Wc =;{ ?ng =,u we8 y^t BYW 'p| "aA
Pc% "Av ?Hv K_g xY;  m< Y%% %LA r@~ O|R cvW &X> xuf "h  {pt &/p ,)- 16_ m6$ GlI
DG1 P&T zB/ k@w &j)  8u I-R pcd Xvg W@Y  CF quE .5& (KZ :iK  CX [p: $<; :Z/ h:_
u"2 <(" b|5 p>d !^T 7z4 O-5 ^rK 4_5 jO* +FF y;; \/R wbw &5&  N7 Gdu 4m= `L/ .">
>Bt g?Y t_% S}w fD' sL3 N&M Lh^ Bn, 1_c }{" 4B\ }Dq {Qz Mjc ,N' b82 }5" ^.j [)Q
~z4 g@S 6_^ FKS {HM ^%=  W] mIY $Q- *J" c'_ _UO lZg 4vB _dh H6  7S7 HCt C*S ov"
Lk9 pyO  "q 7'# cq( kGL 20Z L>l 9WU 9-W )I> <u\ (v* w1g u9& 8;[ Z'9 w4^ OMh J\R
Cy> qnu ,wm ':D *wt -+a AOo ,>W ,Ao =hs HfR B[Z s3% }nv I9u L0L krZ g-B &O3 `MQ
I(q JF8 w Y gK^ ?Vi q:1 3Um qUv JHn skb  bL MQL {=L ;t) iba {(U ?eE d'( Prz pB;
0]W M$+ [WU $8' wP= 0DU %1$ B9m 5sG _li vi5 qeY F8| 0K- P|C nts Hmi _`) pub HFQ
U:Z yDo "LI 33{ }dm l.f xh5 ^>+ j*W b.B D$o non !F, /&+ ")Q [dk w$* ~*& N8; y?G
H6S pg= /<O j_o ;ZR 1@D t=` l\i )'@ D]+ xCl "0^ =rZ sn^ @,P awQ x!q 6C2 ;mP @Xf
AM( <CR _2Q \AC 46> ge2 7L  tBs X*% h00 9'x QYr $Cl jG;  8y *<\ e?O n2J pmS [%7
!mW |3g 3T, t+% `kk %=@ W | Mo8 Oa2 ?!d dwY =JO mA{ s<l N=` L89 @Z? Leo p>| ,YK
w+H %8s r@\ @I*  Tj m(! &gs Q&= Hf% 37i D+9 %Q' |6U ?*  lJ2 Q18 94: 3(L S?X Afj
m*A Qz~ Hd9 Tqn )=8 s?m }2' J(% qs% %i! eus ,hP n?p `qE 2P~ d#p d6n {m{ mHv @:K
h>z Q?% wG" :f" Vsl fb7 p3A J[( {|j ..t @Qx L@Q ;'n S<\ 6c* Mtc YGj I<x zD? PCk
>a" -!g W8S vCg Hoj SkL }|* ZCn 3G0 $Ih 8s6 xpG {zI cpz :V) PFr yaX fA] #I| B5V
du2 JYi hx1 <`U 5E& p~h =mw 5E3 SRz ;+, 3zP rX7 0lX <[$ Om= #_! &-N %Hm >cN yMq
I6T NjU h{m XH6 M$]  94 ;Up NNq  :; Bh+ Na+ <v' $"e Y]5 @s/ Qq2 UyN 3r? YsL \ii
IAX :LY }[( m30 }kY y7v L/v 8XM =U= Sbo Vsf <pZ i\? y(a NLF fU` 'xQ eI< '*t 9TY
G3K cZ& :2X x[; ;|O YPE zxL !qK I=Y 1`u 4tx E4E *k* CI2 Y|P @gl ff& )c- cx1 (]u
b7y ump ?}a ]Fn o+O }vC Iak 1:~ \Q% /[+ tW\ ^QO >#3 Am^ EUX ife idb H%w =.d Hzg
9U9 cvd Exq kSF {ss Spd &Ce \(D ZTp 6kS l!9 2XF 0Z+ N:b *r1 qXb r}E <cS D*d  +N
y2? ,xO 1nx lC. xVj myv P(_ k[Z *8} ;HT jU] sPm lYu b%l ka^ 4R{ :n$ D=F \5{ Cyi
nu4 VnA WxE Zl) ACp ~,* VXm 4rG *!w 6<A yBW L*t `N7 b$k 0;I gfn ]:n @1D e^W hn$
Wps 9H4 Q89 8w8 JTu 045 9E9 puU \P6 >&P wR4 <pH ^MF M}, GJW S7* 62i Rd: hyt P\p
]DR Bzj t}Y Sw* _N| \1[ kQG UB  Wv: [Xh PT( zs8 %Qm !6_ ]*^ WnQ /3r n|h 9NC wpx
6}3 t34 EQp :ZJ r|8 Blx C?W XN< ~]B 7.z 0OK m". C>j N09 RIV iEs 2(r @m_ v"_ ,N_
/]V L$? ~?L UDE `W/ f8` J1u qnB 'F6 &wH hrO xmd WuD )Z8 n ( "6B 59^ T/m WH~ $te
nE0 yLG .vi tM, 6'< N;H PsW 1Kc [#j oPh t|2 ?]< sja 8yV <@; `f1 Kxh {nm -5E Ic/
78~ n8K Y@s q[z iJ[ q\i Z0? rL7 8>T BV: >i~ 9.9 %Dm Y\C Bo- Dz0 b=9 xd, w{N AJf
at9 0~c E<I 49l Z{s fk9 |\@ 2HG 2O" 3 m 7cm Gj5 EaB M9~ .\2 naK +F, /j& *7?

OK, that's a mess.  Let's filter those down to just the 560 ones that consist of just letters:

WiC laK fPi ELS rWf Iqg bdT DYU LzT lZF YNY yyp iRt Fyf DuZ ZJI QcX IDy Zmm dXl
YDF Pzu wpI hpg Qsp TZm tKK YlH nhs ECg AiH Ivn pac ivn yWg Bea jaM JIl kPH rMH
jST pSx cnp zuy QBK ewr ndh xBg wfd unB VDi WBm iBC IvG tID QNS sGx xOX ozM zwp
kcA kJd BMW rnx uni oQW cIN itz QFs Dwh QqV UnJ TLO aJC ukt kpX jRM kWM zIZ cVy
LQX AdG VLP hsg Slu CEu hNl olv XmZ Uus OUK hQN nzG KNk PaC edN Owa zju Ugx czs
TVb mpg llL soU Qyj vPF mYO sDq eVx DWN QeZ xjS wiD SPL zHn eaI Qzg BXa zjs Oxt
lnn JVc VOl QoK GPg edE WGC DRO FlN ssN pNL zmg rAv SES anf GOY xEi tHB zKl NUG
ity Kmj Esj DCl ORt TqK zOL AcT eCJ fQX khd iwv nGT rAQ Fyv QzQ GwW OSN Ixi ENP
sJb yhT lrk vaL wRz Zqz jIo IpB rJZ OLh GRY KCA VOC bcW Lym jno GPl Dew InF QPJ
qPt KJM ahV LuV tFx cWO SHs aEO lAy mHf rGt Hnq gUq qQC GyR bmV IHQ zWU Uym CbI
BWf zQD UTT hvU OOX hGd kXp jrj Buk fBO YMg tcQ nHG hIQ SeO yZa uGx eET BWC MZf
vjj zMl XVZ Hiz TAl kuS eBH exz fwV zRx JEa iSF hXJ Urk kwh gws qvJ pRB uSJ aMG
LiU GPX gFO iVp JEQ iyc VCZ NHG tBi qDX EUu FCg aGI nTX Qno kgk dmx oXT six EXh
Oni drv ysl IXv Gdp lvd UHL anv ijW qcV vCg JJv smc lvU vZg gvP BUY Kuv kMP gWR
tNZ ZMb XFR kEK qoA vUk Wvz qhI CmL gkb XSC NPC swH tkf CUR fFH LfA RDV Ces KQX
MXQ Cur Nti pHx Glq UIg kul mwS jJv kfS cgW lJk uJQ TLq dFv oPS eGo nyY EUo qaB
RLV YVC ZCH foC bCs kuu ZVx uyc XLc xQC Kqg ATZ War HDE LNf UrY uTA MRc xTg GIZ
xSr EwR EUr KlB AJJ iYq TIV aPf LiB rjw Gqn hzY Xcd fzJ svY BrN IFk eal iHp Lbf
mfa Xqp Wxe Gkb SfJ Sxm IOe EOU JEB CBD Ktn Zox gIa mNT Asb XXP Vyq AOZ kxI Xww
yex qAk Zdl yxg jRz Hys Dlx ePU gIx yjh AHd rCQ cKg EPK hUa SKS CKC KGq Yge NSn
Lbg Tav FKs ARc niX uuq dNu xLx BIH Hzy yAU qfd Oqx eHG wZy neb OKB znw wmU pLo
GIF JAz CCm GjY wta usF lUK KpF MDD ESA KiT yxo tpU fAo lXW wyF bor UsX RQg akK
soH BYW cvW xuf GlI pcd Xvg quE wbw Gdu Mjc FKS mIY lZg HCt pyO kGL OMh qnu AOo
HfR krZ qUv JHn skb MQL iba Prz qeY nts Hmi pub HFQ yDo non xCl awQ tBs QYr pmS
dwY Leo Afj Tqn eus mHv Vsl Mtc YGj PCk vCg Hoj SkL ZCn xpG cpz PFr yaX JYi SRz
yMq NjU NNq UyN YsL IAX Sbo Vsf NLF YPE zxL ump Iak EUX ife idb Hzg cvd Exq kSF
Spd ZTp qXb xVj myv sPm lYu Cyi VnA WxE ACp VXm yBW gfn Wps JTu puU GJW hyt Bzj
kQG WnQ wpx EQp Blx RIV iEs UDE qnB hrO xmd WuD yLG PsW oPh sja Kxh AJf EaB naK

Do any of those strings look like a plausible beginning for an English plaintext?  Well, actually, a few do — just at a glance, I see Bea, Dew, War, Cur, six, anv, pac, RIV, CUR, BUY, etc.  I'm sure there are plenty more that might be extended into a meaningful message, even if it's also clear that the overwhelming majority of three-byte strings are not meaningful English.

OK, but according to our unicity distance estimate, there shouldn't have been any reasonably English-like strings in the sample, or at least not more than one or two.  So what went wrong?

Well, the main mistake we made is that the estimate of 1.5 bits of entropy per character is an average for long texts, and measures the entropy per character conditioned on the preceding text — that is, loosely speaking, it says that, given a piece of English text randomly truncated in the middle, you have about a $2^{-1.5} \approx 35\%$ chance of correctly guessing the next character after the break in the text.

However, the first character at the beginning of the message (or at the beginning of the fragment we're looking at) is much harder to guess, and thus carries a lot more entropy — I would guess somewhere around 4 bits, plus one bit for capitalization, if it's not known.  The second character is also likely to be harder to guess than usual, due to the limited amount of context available, so let's randomly allocate it 3 bits, including the possibility that the capitalization might (or might not) change.  (We could calculate more accurate entropy values from a suitable text corpus, but I don't happen to have one handy, so let's just go with these guesstimates.)

This leaves us only $8-5=3$ bits of redundancy for the first byte, and $8-3=5$ bits for the second one.  Assuming that the following bytes have approximately the $8-1.5=6.5$ bits of redundancy assumed earlier, that means that, to uniquely determine a 16-bit key, we need $2 + \frac{16-3-5}{6.5} = 3.23$ bytes, which rounds up to $4$, not $3$.

So let's try the experiment again, this time with 4-byte strings.  For brevity, I'll only show the 133 strings that contain only letters and spaces:

mDJP Ptwu wZIC fXRU OPht rmHg yXp  ffhC IqJl wocL mHxY jUqM reta XzRi EVRY IhIy
FtIB JZYV PhFP OpVy wrWe eoJf XwAN XtcF Bhmj Ipgx abFz MDCg ImqN ehbl Iafe zjfM
DaiH jaKu gQBF qkbi EoIo JzIb IAOT BhFI wYqZ uecv rHhy oKFP INHF WuQA GCmI InIO
YaHR lieX KfQw NzvY qPsn E Xn Xfxa AHyy OZFg qZFE FQsx ffje THPs djhU MFap xRqt
Pkwb cvsU UhfV frvF rfNN eiNt UxTt tTiV duLt MzPC rXUU YSOi vkxk URZj kzYZ RUNB
ZpyD UVpn ysFw temX IkcN UAaR sGDH HKhr YvXo QDSc KUr  YLCv cIjU MvOa eXWi Cqmg
Phed OTnf gbuV aJgL dVH  pabP l wz xNEF oVIv DWzL aUza dqMm ZQEh BcVZ vBTg nGsd
WcGs hUFW Vvrh qcEg RLhi NOuI vKkP KPsT rECZ yaKJ oSnU hkiO CKZN evJH BVJg vlVN
sYrM iXfM LoWf TxOv GNkP

At a glance, the only one of those strings that looks like a plausible start of an English word (let alone a message) is reta.  EVRY and RUNB get close, but if we're going to allow such misspellings or run-on words (which, of course, a practical cryptanalyst should), then we really ought to increase our per-character entropy estimate to account for that.

In fact, one false positive is about what we should expect on average, if our sample length was reasonably close to the unicity distance.  (This is true by definition, since the unicity distance is defined as the length of ciphertext needed to make the probability of a random incorrect key decrypting the ciphertext to a valid plaintext equal to one per the number of keys.)  To reduce the expected number of false positives to a negligible value (say, 0.0001), we really ought to take a look at a couple more characters yet, and see if they still look like English.


How can encryption software accept password lengths which are not one of the AES key lengths? AES comes with key sizes of 128, 192, and 256 bit.

But in Truecrypt or other crypto software we can use passwords of different length, even less than 128 bit or more than 256 bit.

How is this possible?

I imagine that Truecrypt uses a KDF, to derive a 128/192/256-bit key from your password.  This is standard practice.  It's unadvisable to use a password directly, as they're generally low-entropy (predictable), and too short (as you've noted).


Signal protocol: when, and why, is X3DH run again between the same two users? This question concerns the Signal protocol's X3DH key agreement protocol as documented here.

Obviously, if Alice and Bob have never contacted each other before, they need to run X3DH at least once to agree on a key.

However, it is unclear to me why X3DH needs to be run more than once between the same two users: now that they have agreed on a key, and given the Double Ratchet algorithm is used to generate new keys for each message to ensure perfect forward secrecy, why would they ever need to run X3DH again?

Without the need to run a key agreement protocol a second time between the same two users, a simple DH between Alice and Bob's identity keys should suffice, and perfect forward secrecy is not an issue since the protocol would never be run again. Only if the protocol needs to be run more than once would X3DH be called for, to restore perfect forward secrecy.

I imagine this is due to an implementation decision of not committing any keys beyond the bare minimum (private keys for the identity key, signed prekey and one-time prekeys) to non-volatile storage, so that when the app is restarted, the protocol would need to be run again. Can anyone confirm?

it is unclear to me why X3DH needs to be run more than once

They don't. X3DH is only used to initialise the session between Alice amd Bob. Once Root key is derived, X3DH is no longer required until one of them reinstalls the app or changes device.

Together with Diffie Hellman ratchet,  using KDF

Root key derives Chain key and Root key is updated.
Chain key derives Message key and Chain key is updated.

Message key is the one which encrypts the message. For every subsequent message, Chain key is updated to derive new Message key.

The process looks something like this:

A1 and B1 are Message keys.

Even though the session is not reinitialised periodically, Signal documentation actually recommends this but currently it is not used in practice by either WhatsApp or Signalapp.

  4.2. Session expiration
  It may be desirable for devices to periodically replace old sessions with new sessions, for security purposes.

However, long-term keys of the prekey bundle are still rotated but are not reinitialised with the current recipients.

// Time before rotation of signed prekeys (measured in seconds)
//
// Currently we rotate signed prekeys every 2 days (48 hours).
// We generate 100 one-time prekeys at a time.  We should
replenish
// whenever ~2/3 of them have been consumed.

Source

Identity key is kept same unless the app is reinstalled or the device is changed.

As @Natanael, Signal has an option to restart secure session which reintialises X3DH. There is also a multi-device support in Signal which reintialises X3DH between the recepient and the device. It only happens once with each new device until the app is reinstalled.


PBKDF security if all but one keys are exposed I'm trying to understand the security of KDF but stuck with PBKDF case (case 3). Suppose, we have the following settings:

$KDF(SK,salt_1) \rightarrow k_1$

$KDF(SK,salt_2) \rightarrow k_2$

The adversary $A$ knows $salt_1$, $salt_2$, $k_2$ (and maybe even more derived keys $k_j$ for salts $salt_j$). His goal is to get $k_1$. Let even help him by makeing all salts closely related and haveing the same substring. Can $A$ learn $k_1$ from  $salt_1$, $salt_2$, $k_2$?

In the best (and almost unrealistic) case $SK$ is random and uniformly distributed in key space $K$. In this case, we can use some PRF $F$ to derivate a key $k \leftarrow KDF(SK,salt,l):=F(SK,salt||0)||F(SK,salt||1)||...||F(SK,salt||l)$
In such case $A$ can't learn $k_1$, otherwise $F$ is not secure PRF.
Slightly worse case: $SK$ is uniform in some subset of $K$. We need Extract-then-Expand KDF - so we use HKDF. At first we extract $k_{short} \leftarrow HMAC(salt, SK)$ and then expand $k_{short}$ to $k$ by using HMAC as PRF with key $k_{short}$. Again, $A$ can do nothing as long as underlying compression function in a hash is PRF and $SK$ has enough entropy.
Worst case: $SK$ is a password. Suppose it's PBKDF1 and $k \leftarrow PBKDF1(pwd,salt,c) = H^{(c)}(pwd||salt)$

On the one hand, $A$ still should learn nothing about $k_1$ if the hash is secure. On the other, I've got a feeling that he knows enough data to come up with something better than bruteforce. Am I wrong?

In case 3, one must consider that the knowledge of $salt_2$ and $k_2$ (or/and other ones) allows to test a guess of $pwd$ with about $c$ evaluations of $H$. The "brute force" attack becomes doing this with a dictionary of passwords with the most common first. Password crackers using GPUs or ASICs reach astonishingly high hash rates, and for $c$ in the thousands, if a password is memorable, it is best to consider that it is not safe form a well-funded attacker. That's why state of the art is memory-intensive password hashes, e.g. Scrypt, Argon2, Balloon, which make a large difference.

In a multi-target attack (where several $pwd$ each with their associated $salt_2$ and $k_2$ can be attacked, and finding any is a success for the attacker), the attacker should try the most likely $pwd$s on all available instances of the problem s/he's trying to attack before moving to less likely ones. Practical chances of success grow very fast with the number of different users having chosen $pwd$ !

I'm unaware of another weakness of PBKDF1 / $H^{(c)}(pwd\mathbin\|salt)$ that would be exploitable in the situation, and leak any info about $k_1$ without a successful guess of the full $pwd$ (if we leave a aside implementation issues like side-channels).

Note: in theory, the many iterated hashes of PBKDF1 reduce the possible values for the outcome as $c$ increases (see this). A wild guess of $k_1$ with a sizably better than random chance to match is plausible. However, for any hash at least as wide and remotely secure in the ROM as SHA-1, the probability of success remains so low that this is never a practical issue; and truncating the final result of PBKDF1 (which dramatically increases the probability of success of a wild guess) reduces to almost nothing the advantage that could be obtained by exploiting said effect of many iterations.

PBKDF1 successor's PBKDF2 fixes the above theoretical weakness, and allows producing large output, which can come handy. Neither comes with a security argument that it is a strong PRF (as HMAC does). However the main reason to discourage using PBKDF1 or PBKDF2 is that they are among what gives the least resistance to brute-force password crackers for a given level of effort by the legitimate user (number of iterations $c$).


How are security proofs done in ABE Schemes? I have been studying several ABE schemes and I understand the security assumptions and the several types of security models used for the security game between the Challenger and the Adversary.

What still confuses me is the security proof which involves an additional entity "The Simulator" which is usually done at the end of the different papers.

My question is what is the concept behind that security proof? What is the aim and what are the rules that guide the process as I need to understand that to apply it to the scheme I am working on.

N/B - If the question needs any additional details I would be glad to provide them or edit if it needs any changes. Also I have not stated any exact papers as its a general concept that applies to all the schemes I have read about and I am not sure yet if there is any difference in how it is done except for the fact that the different schemes are based on different security assumptions.

Given your answer to my comment, I'll try to give you an intuition about why simulators are used in cryptographic proofs (but as already mentioned, I cannot help much for the particular case of ABE).

Disclaimer: this will be a very (very) informal explanation

Imagin two players, Alice and Bob, performing some cryptographic protocol. Alice has an input $a$, Bob has an input $b$, and both players would like to reveal securely $f(a,b)$ to Alice, for some public function $f$, without revealing anything more. Now, let's say you wish to prove that the protocol is secure for Bob, namely, that Alice cannot learn anything about $b$ by interacting with Bob, except, obviously, for $f(a,b)$. How to show that? Here is the trick: we replace Bob by another entity, which has the two following features:

From the viewpoint of Alice, the behavior of this entity is exactly the same as Bob's behavior. In other words, Alice's view when interacting with Bob is indistinguishable from her view when interacting with this entity. We say that this entity simulates Bob, hence we call it a simulator.
The entity does not know Bob's input at all. We assume that it does only know the output $f(a,b)$ of the protocol.

Now you can already see how the proof goes: when Alice interacts with Bob, from her viewpoint, she could be interacting with the simulator, because she wouldn't be able to see the difference. But this simulator does not even know $b$, it does only know $f(a,b)$. Therefore, Alice cannot learn anything more than $f(a,b)$ from Bob, because if she could, she would be able to tell that she does not play with the simulator (who only knows $f(a,b)$), which she cannot do, according to our first feature.

So, in general, the proof will consist in describing such a simulator, and then showing step by step that its behavior cannot be distinguished from Bob's behavior.

Let us look at a toy example. As you are talking about ABE, which are already quite complex primitive, I assume that you might have already heard of simpler (but still far from trivial) primitives, such as additively homomorphic encryption. But in short, an additively homomorphic encryption scheme $E$ allows you to compute sum and external products inside ciphertexts: from $x,y,E(a),E(b)$, one can compute $E(ax+by)$. Moreover, we say that it is semantically secure, informally, if given $E(x), a, b$, where $x \in \{a,b\}$, no player (without the secret key) can tell whether $x=a$ or $x=b$. Consider the following protocol:

Alice's input: $x,y$.
Bob's input: $a,b$.
Output: Bob learns $ax+by$, Alice learns nothing.
Protocol: Bob sends $E(a),E(b)$, where $E$ is an additively homomorphic encryption scheme for which he knows the secret key. Alice homomorphically compute $E(ax+by)$ and sends this ciphertext back; Bob decrypts it to get $ax+by$.

Let us now show that this protocol is secure for Bob, by showing that Alice learns nothing. We replace Bob by the following simulator: the simulator knows absolutely nothing, pick two random values $a',b'$ and send $E(a'),E(b')$ instead of $E(a),E(b)$ (and does nothing afterward). From the viewpoint of Alice, this is indistinguishable from Bob's behavior, because of the semantic security of the scheme. As this simulator does not even know $a,b$, this shows that Alice cannot learn anything from the protocol.

In this particular, oversimplified case, there are probably more straightforward ways to argue the security. But in more general cases, simulators quickly become unavoidable. Let me try to explain why:

If you want to perform some task securely with a protocol, you can list all the security requirements that you want for this task, and try to prove that your protocol satisfies these requirements. But what if there are requirements that you forgot? Things you did not think of? To avoid this, there is a better solution: describe the task that you want to perform as an ideal functionality For example, for the previous toy example, this could be the following description:

Alice and Bob communicate with the functionality via perfectly secure authenticated channels.
When receiving $(a,b)$ from Bob and $(x,y)$ from Alice, the functionality computes $ax+by$ and sends it to Bob (again, via a secure channel)
The functionality ignores any input which does not have the correct form.

Now, take your protocol, and consider an adversary against this protocol. To show that this protocol is as secure as the ideal functionality that you defined, you will proceed as follows: the adversary will interact with a simulator, which will play the role of an interface between this adversary and the ideal functionality. In other words, the adversary plays the real protocol, but not with an honest player: he plays it with a simulator. This simulator does not know the inputs of the honest players, but can interact with the ideal functionality, playing the role of the adversary. In a way, here is what happen: the simulator tricks the adversary into thinking that he plays the real protocol (by behaving in a way which is indistinguishable from that of honest players), while the adversary is in fact playing against the ideal functionality: the simulator interacts on his behavior with the functionality, and plays the protocol using only the answers he got from this functionality.

If you can exhibit such a simulator, then you have shown the security of your protocol, because whatever the adversary does in the real protocol, he could be interacting with a simulator which does only interface it with the functionality, hence can only learn things that he could have learned by directly playing against the ideal functionality. Recall that this functionality is our definition of a secure protocol for the task we have in mind, so by definition, what an adversary can learn by playing with it is at most what we agree to let him know.

In practice, this require some care in the design of the ideal functionality (using session IDs to avoid attacks in which the adversary plays several versions of the protocol and try to learn things by mixing inputs and outputs, etc). This does also not guarantee that your protocol will remain secure if composed with other protocol (this require a stronger model).

I hope this gave you an intuition. If now you want more practical knowledge on how to do cryptographic proofs using simulation, I agree with user94293 that the recent tutorial of professor Lindell on this topic should be an excellent starting point (I have to admit I have not read it yet, but it seems safe to assume that it'll be a good tutorial, given its author).

If you have any question, please don't hesitate. If anyone wants to point out parts of my explanations that are prohibitively informal and should be removed/rewritten, I accept it too :)


How to find a collision with a given prefix and a known key in an AES ECB symmetric block cipher? I should be able to find a collision for a vulnerable hash function which uses AES ECB given a prefix, but I am unable to find a reasonable solution (besides brute-force attack).

The hash function is really simple, it uses AES ECB with a known IV with all 1's. The result is then bitwise XORed and used as key for next ciphering block (if any). More formally:
$$S_0=1^{128}, S_i=\operatorname{AES}_{S_{i-1}\parallel S_{i-1}}(M_i)\oplus S_{i-1}$$ with $M_i$ being the current 128-bit message block, AES using a 256-bit key and the $S_i$ of the last message block being the output.

I have been reading about the Chosen-prefix collision attack, but my case is slightly different (and even easier) because what I search are two words $w_1$ and $w_2$ that, given a known prefix $p$, $\operatorname{hash}(p \| m_1) = \operatorname{hash}(p \| m_2)$ with $w_1 = p \| m_1$ and $w_2 = p \| m_2$ and $w_1 \neq w_2.$

but my case is slightly different (and even easier) because what I search are two words $w_1$ and $w_2$ that, given a known prefix $p$, $\operatorname{hash}(p \| m_1) = \operatorname{hash}(p \| m_2)$ with $w_1 = p \| m_1$ and $w_2 = p \| m_2$ and $w_1 \neq w_2.$

Actually, if two messages differ only in the last 128 bit block, they will always hash to different values (and hence they will be no such collision).

That is because, when processing the common prefix, the two messages will have identical $S_{i-1}$ values; the resulting hashes will be:

$$AES_{S_{i-1} || S_{i-1}}( M_i ) \oplus S_{i-1}$$

$$AES_{S_{i-1} || S_{i-1}}( M'_i ) \oplus S_{i-1}$$

These will be the same only if $AES_{S_{i-1} || S_{i-1}}( M_i ) = AES_{S_{i-1} || S_{i-1}}( M'_i )$, and because $AES_{S_{i-1} || S_{i-1}}$ is a permutation, that'd happen only if $M_i = M'_i$ (and hence we're hashing the same message, hence not a collision).

Now, if we are allowed to modify the problem (for example, if the two messages have different prefixes, if the 'word' inserted at the end is longer than 128 bits, or alternatively if the resulting hash is truncated to smaller than 128 bits), then it becomes easy.  However, as stated, it is impossible (not infeasible, but logically impossible).


How does Signal Messenger's Safety Number Works? Why do they recommend the user to verify the 60 digit code in person or via other medium of communication.

How is the security code generated and work on Signal and Whatsapp Messanger?

Here is a detailed blog post about the safety numbers:
https://signal.org/blog/safety-number-updates/

They are unique per conversation and basically consist of hashes of your and your contact's public long-term key.

You should compare them if you want to be sure that there is no man-in-the-middle.


Curve25519 simple key exchange approach What is a simple approach in Curve25519 key exchange in basic steps?

Alice and Bob choose their secret scalars $a,b \in \{0,1\}^{|p|}$.
They compute their public keys $Ga$ and $Gb$ and send the public key to the other.
Alice computes the shared key $k = \text{kdf}(Gba)$ and Bob computes the shared key $k = \text{kdf}(Gab)$.

They can use this established key $k$ as their shared symmetric key. I.e. Use it as the key for AES-PMAC-SIV to send variable-length messages that are both authenticated end encrypted.

Eve is allowed to learn all public keys and ciphertexts. Assuming that at least the Computation Diffie-Hellman and Discrete Logarithm problems are hard, then she cannot recover the shared key.


Nothing-up-my-sleeve numbers standard Premise
Several cryptographic primitives employ randomized numerical constants. To avoid suspicious that the designer selected such constants in order to plant a backdoor, "nothing-up-my-sleeve numbers" are used. These are numbers constructed from the first digits of some important constants, like $\pi$, $e$, $\sqrt{2}$, ... so that they do not appear to be well-crafted to hide a backdoor.
The Problem
However, designers of different systems use different constants. Below some examples copied from the wikipedia's page:

Small roots of small integers (SHA-1, SHA-2)

$\sin 1, \sin 2, \dots$ (MD5)

$e$ (DFC)

$\pi$ (Blowfish and many other)

$1/\pi$ (ARIA)

0x123456789ABCDEFFEDCBA9876543210 (KASUMI)

ASCII string "expand 32-byte k" (Salsa20)

But with enough degrees of freedom, it is clear that nothing-up-my-sleeve numbers lose their purpose. For example, who does guarantee that the sentence "expand 32-byte k" was not selected among thousands of similarly innocent ones ("expanding 32-byte k", "expansion of 32-byte k", "32-byte expanded k", ...) in order to hide a backdoor? Likewise for numerical constants.
The Question
In light of the previous considerations, was a "nothing-up-my-sleeve numbers standard" ever proposed? If not, why not?
A very simple standard could be: "A cryptographic primitive employing a randomized constant $C$ (if there are more randomized constants, $C$ is their binary concatenation) must fix $C$ to be the first digits of the binary representation of $\pi$."

A (probably weak) reason not to use a standard is that some nothing-up-my-sleeve numbers may serve some sort of purpose.  As an example, you cannot change Salsa20's constants to anything, it must be sufficiently asymmetric.  It's feasible to presume that another cipher may have a different set of requirements
As per this answer:

Salsa20 has strong rotational symmetry. The main point of these constant is that they're not invariant under rotations, introducing an asymmetry. The precise value isn't very important, as long as it's sufficiently asymmetric.

The answer goes into further detail, quoting DJB himself on the matter.
This answer also details several cryptographic constants, and the padding constant for HMAC is similarly designed to be asymmetric:

The padding constants for HMAC, 0x36 for ipad and 0x5C for opad, are repeated (for the hash function's block size) and XORed with the key to generate the prefixes for the two hashing steps. 0x36 = 0b00110110 and 0x5C = 0b01011100 - these two values are about "as different as possible", to avoid any attacks which rely on a similar hash state after the key block for inner and outer hash. This is mainly a heuristic, as far as I understand.


Should the seed of CSPRNG produce the same random number? Assume we are designing a CSPRNG to be used in encryption like that used for ECC-based cryptography.

Is it required that the seed always produces the same random number always? Or should it be  designed to produce different numbers, making it even more secure?

The seed is the source of entropy for any CSPRNG. A CSPRNG is a pseudo random number generator. The "pseudo" part in the name explicitly means that it solely depends on entropy delivered from outside the algorithm using one or more seeds. So a CSPRNG, by definition, cannot be designed to produce "different numbers", as the outcome solely depends on the seeding of the algorithm.

Maybe the term "deterministic random bit generator" or DRBG better catches this meaning - most CSPRNG implementations do also primarily output pseudo-random bits rather than pseudo-random (ranged) numbers.

Now CSPRNG implementations in many runtimes depend on seeding by the operating system. Such seeding may even take place if a user provides a seed themselves. Basically such systems treat the seed as an additional source of entropy, making the next retrieved values depend on both the entropy sources, by mixing them into the state.

Furthermore, CSPRNG algorithms or algorithm implementations may be configured (explicitly or implicitly) to perform re-seeding after a certain amount of bits or calls. In that case the CSPRNG performs a callback to the system that provides the (initial) seed to retrieve additional seeds, which are then mixed into the state. A user may usually also call a method to add seeds or fire a request to re-seeding.

Often CSPRNG's are not explicitly required to return the same random bits if the amount of bits are different between calls. Even if the CSPRNG is in the same state, asking for 8 bits and then 16 bits may result in different values than asking for 16 bits and then 8 bits.

CSPRNG's may also change their implementation slightly, for instance they may generate numbers in a range using several different methods.

All this makes using a CSPRNG of a runtime system very dangerous if you expect to having it generate the same sequence for the same seed, and using a CSPRNG for such purposes it a huge red flag within any design - unless the CSPRNG is explicitly designed for such purpose.

If you do need a predictable stream then you are better off using a KDF (for relatively small output), a XOF such as SHAKE-128 or SHAKE-256 or indeed a stream cipher. Beware though that crypto-systems such as EC may also use the bits in different ways, so if those systems change implementation, you'd still get different results.

Generally, however, a well seeded CSPRNG is all you need to implement a cryptosystem that requires randomness.


Pairing Field size as security parameter I have read Pairings for cryptographers: It states that the groups $G_1$ and $G_2$ are groups of points on the curve and the group GT is a subgroup of the  multiplicative group of a related finite field $F_{q^k}$. l is the order of these three groups. It then states that the sizes for $q$ are more comparable to RSA rather than like RCC. I implemented a type D curve. Lynn states for the type D curve that 170 bit for q (and l) should be sufficient.

I have problems to understand this all since I am missing some mathematical background. The size of q is very much depending on the type of curve. Or is Lynn's statement just outdated? When I implement a scheme based on this particular "type D"-curve, how do I define the security parameters and how do I justify my decision?

I would have thought, that the group operations in $G_1$ are the fastest and all others are slower, therefore this size matters. But now I think this is too easy and wrong.

Thats a bit outdated as for your choice of setting (with $k=6$) the 170 bit will give you 1020 bit security in the subgroup of $F_{q^6}^*$.
In your case for embedding degree 6 I would at least take 224 bits which would give you 1344 bits in the multiplicative subgroup of $F_{q^6}^*$ or you even go to 256 bits which will give you 1536 bits. Anyways the setting with embedding degree 6 will give you not an optimal efficiency-security tradeoff as you have to take far higher security levels in the curve to achieve acceptable security levels in $G_T$.
The choice of Baretto-Naehrig curves will give you the optimum security-efficiency tradeoff (they have $k=12$) today and they are for instance implemented in the RELIC toolkit.
You may look here what parameters for elliptic curves and multiplicative groups of finite fields are recommended today by different institutions.

Update (2021): As mentioned in the comments, already in 2014 the parameters mentioned above for MNT curves only gave security (far) below 100 bit. For an up to date reference on parameters one can look here: https://members.loria.fr/AGuillevic/pairing-friendly-curves/


What is the complexity for attacking 3DES in linear or differential cryptanalysis? I know that 3DES is NOT vulnerable to DC , LC .
But is it because the attacks  requires too many  input\output pairs ?
Or because it's impossible ? (i.e requires more than 2^64 pair )

"Not vulnerable" is not how I would describe it, but my understanding is that the existing attacks on DES cannot directly not work with 3DES.

At the moment, the best attack against single DES is a linear attack which requires $2^{43}$ plaintext-ciphertext pairs, and has a time complexity of at between $2^{39}$ and $2^{43}$ operations.

Linear cryptanalysis works by trying to approximate the functionality of the cipher with some linear function, e.g. "if I plug all of the input and output bits into this polynomial I discovered, I can determine the value of the 26th bit of the key with a confidence of 72%". Given such approximations, an attacker with access to enough plaintexts and corresponding ciphertexts for a single key may be able to recover the entire key, or enough of it to make a bruteforce on the remainder feasible.

Many block ciphers, including DES, introduce non-linearity with an S-box. While it may be possible (or even trivial) to produce linear approximations of a single round of a block cipher, doing so for larger numbers of rounds becomes significantly more difficult. Assuming a good design, as you add more rounds, the number of possible internal states of the function increases, and the statistical significance of linear approximations decreases. This increases the number of plaintext-ciphertext pairs and operations you need, often to the point of making it less feasible than a brute-force attack.

Differential cryptanalysis works in a similar way. By observing how changes in input propagate through each round to the output, it may be possible to identify behaviours that leak information about the round keys. For example, one might select a pair of similar message values $m_1$ and $m_2$, and then compare $m_1 \oplus m_2$ and $f_r(m_1, k_r) \oplus f_r(m_2, k_r)$, where $f_r$ and $k_r$ are the round functions and round keys respectively. Statistical analyses of each separate round, in relation to their reactions to small changes in input, can be combined together to demonstrate properties that can be used to determine information about the values of the round keys in the full-round version of the cipher, or in a reduced-round variant (though this would not constitute a break).

The thing to keep in mind here is that attacks such as these rely upon the attacker having access to a large number of plaintexts and their associated ciphertexts for a key that they wish to recover. Removing this ability, or inhibiting it sufficiently, makes it incredibly hard to find practical attacks against even mediocre ciphers.

Now, the important question to answer here is as follows: can the existing attacks on single DES be reconstructed in a way that allows them to function against 3DES, where the attacker only has access to an oracle against the entire encryption process? (i.e. the values of the intermediate steps in 3DES are unknown to the attacker). The answer is essentially no. Since the attacks require the attacker to know a large number of plaintext-ciphertext pairs for each DES operation, but the intermediate values of the 3DES operation are unknown to the attacker in this scenario, the original attacks are no longer directly relevant - it isn't possible to just "run the attack three times".

Instead, new attacks had to be formulated against 3DES, using the same observations in previous attacks as building blocks, but applying them to a full 3DES operation. 3DES can be thought of as a 48-round variant of DES, as each round of DES is identical (aside from the key schedule, but that is irrelevant for LC and DC attacks). This now means that a full-round attack against 3DES requires linear approximations across all 48 rounds, or differential properties that can be correlated across the full 48 rounds. This is remarkably difficult to do - much moreso than against single DES itself.

The "typical" attack against triple encryption is what's known as a meet-in-the-middle attack. In such an attack against 3DES, we treat each DES operation separately, and attack a single plaintex-ciphertext pair. First, we perform decryption operations against the ciphertext for every possible $2^{56}$ keys, and store the resulting decrypted blocks in a list. This requires $2^{56} \times 64$ bits of space, or 512 petabytes. Next, we perform the first two DES encryption operations against the plaintext for every possible key (i.e. brute-force the entire 112-bit keyspace) until we reach an output that matches an entry in the previously computed list. Once we find a match, we know we've found the correct key. The time complexity of this attack is $2^{112} + 2^{56}$, which can be approximated down to $2^{112}$ due to the massive difference in exponent.

This basic idea has been improved upon somewhat for DES specifically - the best known attack requires $2^{32}$ known plaintexts, $2^{113}$ operations (consisting of $2^{90}$ DES encryptions and the remainder much faster operations), and $2^{88}$ memory. While, numerically speaking, this has more operations than the direct meet-in-the-middle, the vast proportion of those operations are much faster in practice. As such, the number of operations itself doesn't tell the full story in terms of actual computational cost, and the attack is faster than a naive meet-in-the-middle.


Shamir Secret Sharing and Diffie-Hellman procedure Alice needs to share an already generated numeric secret $s$ with Bob and she doe not want the world to see it. The problem is that she has never contacted Bob before.

I thought Alice and Bob could generate a line à la Shamir Secret Sharing so that $$q(x)=s+\alpha x.$$

To agree with $\alpha$ Alice and Bob could implement the original Diffie-Hellman protocol for key exchange. Finally Alice could just send $q(1)$ to Bob and he could compute $s$ as $$q(1)-\alpha*1=q(1)-\alpha=s.$$

Theoretically even if Eve could see both the values sent in the clear by the Diffie-Hellman protocol and the value $q(1)$, Eve could not compute $s$ from them.

Is this method already used used somewhere? Do you know some literature which prove this to be secure?

This protocol is insecure because the original Diffie-Hellman method can be exploited by man-in-the-middle attacks.

For this reason, you should never use Diffie-Hellman alone.


How can you determine how long the MAC for GCM must be? I want to use AES-GCM to encrypt 7 Byte data chunks.

A 16 Byte MAC seems like overkill to me and the library I'm using gives me the option to make the MAC smaller.

Are there any criteria for choosing the length of the MAC or are fewer bytes always less security?

In Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC Appendix C, Table 1 & 2 NIST gives the recommended maximum number of invocations of the decrypt function of GCM for different message lengths using a MAC of 4 and 8 Byte.

My message length of 7 Byte cipher text + 0 Byte additional authenticated data (AAD)  enables me to decrypt $2^{22}$ and $2^{32}$ messages respectively, before having to change the symmetric key.

Since in my application I want to send $2^{32}$ messages before I'll have to change the key, I'll have to use 8 Bytes.


Which public key encryption scheme is re-randomizable? How can I re-randomize an encryption scheme? Which public key encryption scheme is re-randomizable?
Is there any library for re-randomizable encryption scheme?
If not, how can I re-randomize a given public key encryption scheme?

I cannot find any papers about re-randomizable encryption.

I will start with an example and then comment on a natural general way to achieve re-randomization:

ElGamal: Let’s say we have a multiplicative written group $G$ (suitable for ElGamal) with public key $h=g^x$ and $g$ generates $G$ (or some prime order subgroup of $G$).
Any library that implements ElGamal encryption can do the following, although there may be no explicit function to do this: Take some ciphertext $(g^r,mh^r)$ for some message $m$ under public key $h$ and (since ElGamal is multplicatively homomorphic) do a component-wise multiplication with an encryption of the identity $1$ in $G$, say $(g^k,h^k$), with $k$ chosen uniformly at random. This gives you $(g^rg^k,mh^rh^k)=(g^{r+k},mh^{r+k})$, which is a re-randomized ciphertext to the original message $m$ under the public key $h$.

Generically, any public key encryption scheme that is probabilistic and homomorphic will let you re-randomize a given ciphertext by using the homomorphic property with a ciphertext to the identity of the respective group.

To generate the ciphertext of the identity element you obviously need access to the respective public key, i.e., you have to know under which public key the respective ciphertext has been produced. This can be avoided by extending the regular ciphertext with an encryption of the identity, as e.g. done in universal re-encryption.


Question about IV/initialization vectors I found some code to get crypto-js to encrypt data in the browser, and with a pointer from someone on SO, it now decodes data as well.

My next question is about the use of an IV; is an IV like a salt where it needs to be generated from a cryptographically secure RNG, or will any data do like, a timestamp?

And from my reading, an IV does not need to be secret - if your IV is 16 bytes long, you take those 16 bytes, append the text to it that you want to encrypt, and then can publish both the IV and cipher text. Upon decrypting, you would check that the first 16 bytes of plain text match the IV, and then discard them from the resulting plain text.

Am I understanding this correctly? Will any unique data (to each cipher text) be useful for an IV, or should I be looking for a method to generate IV's (on the client side, which means it could potentially be substituted) in a secure manner?

Thanks!

PS - this is for a personal project/learning experience, not a product that's advertised as being secure :)

It depends on the encryption mode you're using:

For CTR, CFB and OFB modes, the IV simply needs to be distinct for every ciphertext encrypted with the same key.  (For CFB and OFB modes with less than full-block feedback, there are certain "weak IVs" that should also be avoided.)
For CBC mode, the IV needs to be unpredictable.  One way to achieve that is to generate the IVs randomly, although other methods (such as encrypting a counter with the raw AES block cipher — preferably with a separate key, if there's any chance that an attacker might be able to control the counter — and using the result as the IV) can also be used.

In any case, the IV does not need to be kept secret.  If it had to be secret, it would be called a key instead.

Also note that none of the traditional encryption modes mentioned above are secure against chosen-ciphertext attacks (i.e. attacks where the attacker modifies the ciphertext, or makes up fake ciphertext out of whole cloth, and sends it to the recipient to see what happens).  In particular, all of them (but especially CTR and OFB) are malleable, so that an attacker who can flip bits in the ciphertext may be able to flip corresponding bits in the plaintext.  Unprotected CBC mode is also vulnerable to padding oracle attacks, unless special care is taken to prevent them (and, even then, it still remains somewhat malleable).

To protect your messages from modification and to avoid such chosen-ciphertext attacks, you'll need to either use an authenticated encryption mode, or compute a message authentication code (such as HMAC) on the ciphertext (and IV!) after encryption (and verify it before decryption).


Difference between encrypting something and hashing something What is the difference between encrypting something and hashing something?  in what situations would I want one or the other?

(I am new to cryptography, so hopefully I wouldn't say anything wrong. The following I hope should help give an idea of differences).

In general you always have a plaintext or something that you want to keep secret. This might be a message or a file or a password.

Encrypting: encryption transforms the plaintext into something that cannot be understood - something that doesn't have any meaning. Something unintelligible. You encrypt the message/plaintext by using an algorithm and a key. The output (the ciphertext) always depends on the key. The essential thing about encryption is that you can always recover the plaintext (if you know the key/password), and given a key/password you have only one plaintext. So you can think of encryption/decryption as a way to move back and forward between you plaintext and your cipher text (using a key).
Uses: Encryption is good if you say have a message to send to someone. You encrypt the message with a key and the recipient decrypts with the same (or maybe even a different) key to get back the original message.

Hashing: hashing turns something (usually a key or a password) into a (usually fixed length) string of characters. For example your hashing algorithm might always produce a string that is 8 bytes long. As with encryption you transform something intelligible into something unintelligible. One might call the product of the hashing the hash codes of the hash sums. One difference is that hashing two different messages might produce the same hash values. So you cannot decrypt something that you have hashed. But even though you can't decrypt a hashed value, it is (or it should) in general hard to make two messages that have the same hash value. Another difference is that hashing doesn't require a key.
Uses: One use of hashing is if you want to send someone a file. But you are afraid that someone else might intercept the file and change it. So a way that the recipient can make sure that it is the right file is if you post the hash value publicly. That way the recipient can compute the hash value of the file received and check that it matches the hash value.


Why are there $2^{56}$ possible DES keys when there are 64 key bits? On forums I read DES has $2^{56}$ possible keys so it takes x times to brute force it with hardware x.
But there are 64 total bits of which are 8 parity bits.
But those parity bits are a 1 or 0, right?
So since you still have to calculate the parity bits and since they aren't always the same bit, doesn't this mean that you have $2^{64}$ possible DES keys?

Each 56-bit key has a unique 8-bit parity value. For this reason there are only $2^{56}$ keys.


How long would it take to crack a double hash if salt and final hash are public? I have a hash of a file $H_1$ and then I add salt and rehash it: $H_2$. I make my $H_2$ and salt public and I use my $H_1$ as a password. How long would it take for this to be cracked with someone trying to figure out all the combinations of the 128 characters and adding the salt to get $H_2$?

So they are trying to figure out $H_1$ and adding salt to confirm that it matches $H_2$. As $Hash(H_1 \| salt) = H_2$, how long would it take to crack the 128 characters to find the $H_1$ that corresponds with this combination?

Please assume SHA3-512 as hash function.

A SHA3-512 hash outputs 512 bits. If you use that as input to the second application of the hash then it takes $2^{511}$ tries - on average - to brute force it. This is obviously far out of range of a practical attack.

The one thing that could be performed is to try to guess the input of the first hash: the file content. If this can be guessed then the scheme would be broken. The file could be very short or it may just not contain enough entropy, regardless of the size. For instance, if you'd use the copy of the MP4 version of Kill Bill 1 and somebody knows that you like the movie, the hash may be relatively easy to guess.


How to calculate the probability to get two random numbers equal from the same generator I have deterministic random bit generator (DRBG) to generate a random numbers in which it is 10 byte value and I want to turn this algorithm twice, what is the probability to get the two random equal and what is the maximum time to try to get this result ?

Well, to start with, if you run two DRBGs with the same seed, the probability of getting the same values from both of them is obviously 100%.

Assuming different seeds, the probability of getting any specific n-bit string is $1/2^n$, so getting the same 10-byte value twice in a row would happen with probability $\frac{1}{2^{10*8}} \approx 1/(1.2089*10^{24})$, assuming a perfectly random (uniformly distributed) DRBG.

If you just want to run the DRBG a number of times until any two results collide, we get into the area of the birthday paradox. I don't have the result for 80 bits (10 byte) at hand, but for 64 bits, to have a collision with the chance of 50% you would have to try $5.1 * 10^9$ invocations. For 128 bit, that grows to $2.2*10^{19}$ (results from this table). This will get lower if your DRBG is not perfectly random, but biased towards certain values.

As for the time this would take, it depends on the performance of the DRBG and your machine, but I think "quite a while" would be a good first guess. If you assume 1 ms for each invocation (including comparison), 64 bit would take around 60 days, while 128 bit would already take around $697\,615\,423$ years (for a chance of 50% for a collision). Yours would be somewhere in between.

Edit: If you want to hit a specific value, you will have the same chance of $1/2^n$ on every invocation. That's a Bernoulli process, and it's a bit of a headache.

Say you want to know what your chance is to hit one matching result in n tries, and your probability of success for each try is $p$ (that would be the $1/(1.2089*10^{24})$ from above). You would calculate $1-((1-p)^{n})$. The inner $(1-p)^n$ basically gives you the probability that you will not hit it on any of your $n$ tries (i.e. you will fail every time). You invert that by taking 1 minus that result and you get the probability of finding at least one match. You can use that to estimate how many attempts it would take.

There probably is a way to estimate the number of attempts to get to a certain probability of success, but I can't find it right now. If anyone knows, feel free to edit this answer.


Proof of ignorance to prevent "double-spend"? Suppose I have some knowledge that I want to transfer securely from Alice's computer to Bob's computer, and prove that future breaches to Alice's computer will not reveal that information to someone else. I.e., I want to be able to treat that information like a physical object, which can be moved, but not simply copied.

I have discovered that Proofs of Ignorance are a thing, but I don't really understand them very well. So, for any arbitrary piece of information x, is there any protocol between Alice & Bob in which Alive reveals x to Bob (thus proving that she did in fact know it at one point), and then subsequently prove that Alice has forgotten?

From the linked paper on Proofs of Ignorance:

  Intuitively, it seems impossible, since one can always pretend to be ignorant. We explore the settings in which one could give a convincing proof of ignorance. As a thought experiment, suppose that Alice holds a locked box and wants to convince Bob that she does not know the contents inside the box. In general, Bob has no reason to believe Alice unless Alice provides some evidence on how she got the box
  in the first place. Suppose Bob trusts that Charlie gives locked boxes without revealing its contents and suppose that Alice is able to prove that she got the box from Charlie, then Bob might be convinced of Alice’s assertion.

The paper's concept of a proof of ignorance is only applicable to certain settings where a player can prove that they never had the information to begin with. It doesn't offer a way for a player to prove that they've forgotten some information they knew at some point. I don't think there's any sure way that you could prove that.

If you know the knowledge is intended for Bob from the start, could you not encrypt it directly to Bob? If you and Bob had a pre-shared key, then you could symmetrically encrypt the knowledge with that key, or if Bob had published a public key, then you could asymmetrically encrypt the knowledge with that key. Alice wouldn't be able to make any sense of the information, but could still be able to relay the encrypted information to Bob.

There are some possible reasons that the encryption-based scenario wouldn't work for your case:

You don't know yet who will be "Bob" when you give the information to Alice (maybe Alice chooses who Bob will be), and Alice needs to be able to complete the process without your involvement.
Your only communication channel to Bob is a one-shot communication through Alice, so you can't share a key with each other ahead of time or after the fact.

If the encryption-based solution doesn't work for you, then this question otherwise seems like a more specific version of How to use proof of lack of knowledge?. That question is to prove a lack of knowledge, and this question is about proving a lack of knowledge that was previously held.

I provided an answer to that question based on incentives, but that answer is less than perfect for this scenario because it also incentivizes Alice to retain the information and claim the bounty.


Compute euclidian distance on encrypted data The scenario is described as following: Let $A$ an user that is transmitting an encrypted (with its own public key $PK_A$) data vector containing its position as $p = Enc(PK_A, [x,y])$ towards a group of users $U = [u_1, u_2, \dots, u_n]$.

Is it possible that each of these users belonged to the group $U$ positioned at different distances from $A$ can compute respective the euclidian distance on it (on the encrypted data that they received I mean)?

No, not in the system as described.

One sufficient reason: in any scheme matching the standard goals of public-key encryption, including homomorphic, nothing about information encrypted with a public key can be determined from the cryptogram without the matching private key. Thus $p$, encrypted under A's public key, can't be used by others (not knowing A's private key) to determine the distance of A to another point.

The normal thing would be that A signs her position (and date/time) with her private key, encrypts the outcome using other user's public keys, and trusts them not to collude to find her location. Such scheme allows the users to determine their respective distance to A, and protects them from third parties trying to misinform them about A's position.

The non-collusion hypothesis is necessary for geometrical reasons even if the devices used to determine the distance to A are designed not to leak her location. That's because multilateration¹ allows three users B, C, D at known locations and knowing their distance to A, to determine A's position, defeating the purpose of encryption.

That's a hard limit. Fully homomorphic encryption could allow a third party to compute the encrypted distances from the locations encrypted with the same public key, without knowing the locations or distances; but getting at the result requires the private key. That's about all I can imagine towards the question's goal.

¹ Essentially, assuming A,B,C,D are on a plan, A sits at the intersection of 3 circles of centers B, C, and D, of radius their respective distances to A. Two users are often enough to narrow A's position to just two locations, and perhaps one of them is unlikely. If the angles BAC, CAD, DAB are not overly acute, the third user's info narrows to one location, and tends to make the estimation of A's location precise, with an incertitude on that only a few times the incertitude on the positions of A B C D. The technique also works on a sphere of known radius, or in three dimensions with one extra point.


Let F be a PRF, how to prove F3 is PRF? Let $\operatorname{F}$ be a $\operatorname{PRF}$, how to prove $\operatorname{F^3_{k_1,k_2}}(x) = \operatorname{F_{k_1}}(x) \oplus \operatorname{F_{k_2}}(x) $ is aslo a $\operatorname{PRF}$?

This cannot be a PRF in all cases, because in the edge case where K1 = K2, the output of F3 will be 0 for all x.


Forging a valid tag for an arbitrary message when you have some knowledge about the key I am using  HMAC-SHA256 with a 128-bit key. Assume my key generator leaks some information to an adversary. Hence, the adversary can predict the key with probability $\alpha$. Can I say that the adversary can forge a valid (message,tag) pair with probability $\alpha$?

[Suppose] the adversary can predict the key with probability $\alpha$.  Can I say the adversary can forge a valid (message,tag) pair with probability $\alpha$?

It's not quite $\alpha$.  Write it out with the chain rule:

\begin{align*}
  \Pr[\text{forgery}]
  &= \Pr[\text{forgery} \mathbin\& \text{guessed key}]
     + \Pr[\text{forgery} \mathbin\& \text{didn't guess key}] \\
  &= \Pr[\text{forgery} \mid \text{guessed key}] \Pr[\text{guessed key}] \\
  &\qquad + \Pr[\text{forgery} \mid \text{didn't guess key}]
              \Pr[\text{didn't guess key}].
\end{align*}

Under your premise, $\Pr[\text{guessed key}] = \alpha$, so $\Pr[\text{didn't guess key}] = 1 - \alpha$.

Exercise: Figure out what $\Pr[\text{forgery} \mid \text{guessed key}]$ and $\Pr[\text{forgery} \mid \text{didn't guess key}]$ are.  Hint: Model HMAC-SHA256 as a uniform random function.  What's the probability any two prescribed inputs $m \ne m'$ collide under a uniform random function?  (Then add a term at the end for the distinguishing advantage of the adversary against HMAC-SHA256.)


Do Gap-CDH groups exist? A Gap-CDH group is such that, given group elements $g, a = g^x, b = g^y$, it is hard to compute $g^{xy}$, but, given a group element $c$, easy to verify if $c = g^{xy}$. While such groups have been proposed, and it is obviously feasible to define a group where Decision Diffie-Hellman is demonstratively easy, exactly what grounds exist for the conjecture that Computational Diffie-Hellman is hard in such groups, beyond the observation that no known algorithms for solving it yet exist?

Are there ways to reduce the hardness of CDH in a Gap-CDH group (in general or some specific group), to the hardness of CDH in a group that has received more thorough scrutiny over the years? For instance, does there exist a group $G$, such that DDH is easy in $G$, and there exists a proof that the ability to solve CDH in $G$ implies the ability to solve CDH in $Z_p^*$ for a suitably large prime $p$?

The closest that I can think of is a "symmetric bilinear group" (a.k.a. Type-I pairing group) that was popular when bilinear groups were first introduced. This is actually a pair of groups $(G, G_T)$ together with an efficient non-degenerate bilinear map $\otimes: G \times G \to G_T$. Obviously DDH is easy in $G$, since one can on input $(g, U, V, W) \in (G_1)^3$ test whether $g \otimes W = U \otimes V$. But the pairing will not necessarily help you compute CDH in the source group, since the map $(\cdot \otimes g)$ is not meant to be easy to invert.

These kinds of groups are constructed based on various types of elliptic curve, my intuition is that a pairing "out of" a curve group won't help you compute new elements in the group itself.

This kind of group appeared in Boneh, Boyen and Shacham (eprint 2004/174) where they used the Decision Linear assumption instead of DDH, since DLIN can be hard even in the presence of a pairing.


Security of Homomorphic encryption schemes Usually for cryptosystems the security is denoted as a $2^n$-bit security such as 256-bit, 1024-bit, 2048-bit etc whereas I came across homomorphic schemes mentioning 80-bit and 96-bit security.

Is this secure enough? Why does it not follow the $2^n$-bit security?

Why does it not follow the $2^n$-bit security?

They follow the usual way of describing schemes, i.e., $n$ bits of security means $2^n$ operations to the best attack. So, taking $n = 80$, you impose "an effort" of $2^{80}$ to the attacker.

  Is this secure enough?

This is a tricky question. That depends on what you want to do with the scheme and how powerful the attacker is supposed to be.

Anyway, I think the main reason to have $n = 80 $ in this kind of paper, is that homomorphic encryption schemes are very expensive and authors just want to show a proof of concept. Anyone that wants to use these cryptosystems is free to instantiate them with larger values of $n$.


Ideal passphrase length: old diceware method (5 words) vs. your Bitcoin wallet.dat passphrase lenght (8 words) and doubling passwords? I made a cool 5 word passphrase back then using the old Diceware method and use it as a master password. The question is as computing power increases will we need to add more and more words to our passphrases which we will eventually forget? I'm in my mid 30s, will passphrases be enough in my lifetime? :) So back then, Diceware suggested just 5 words, not the original Bitcoin QT client recommends 8 words. Will theoriginal 5 words from the Diceware age will serve me in the Bitcoin age?

I don't really want to mess around with a Yubikey. Heck, I Googled it and didn't really managed to find out what it is, what it does. Maybe I'm not the target market. I'm just a simple user. Carrying around a Yubikey would also be a red flag in my eyes. He has secrets!

How effective is doubling a passphrase? Like I have now [passphrase] and simply doule it: [passphrase][passphrase]. So I don't really have more stuff to remember, just more stuff to type. That might serve me for a time.

Oh, another interesting question as well: let's say I use one exact password on many similar forum pages. Will this generate the exact same hashes if they use the same forum engine? I know, you can't recover the password from the hash, but they may find same hash = same guy, right?

Psl. form your answers in a newbie language, thank you!

I made a cool 5 word passphrase back then using the old Diceware
  method and use it as a master password. The question is as computing
  power increases will we need to add more and more words to our
  passphrases which we will eventually forget? I'm in my mid 30s, will
  passphrases be enough in my lifetime? :) So back then, Diceware
  suggested just 5 words, not the original Bitcoin QT client recommends
  8 words. Will theoriginal 5 words from the Diceware age will serve me
  in the Bitcoin age?

Bitcoin (well, the wallet software, anyway) is being a bit conservative. A 5-word passphrase might be a bit on the low side, but if your words have been chosen randomly from some dictionary with about 7.5k words, as claimed on the Diceware page, you should be safe, as this comes out at roughly $64$ bits of entropy. This should remain a strong passphrase for the next decade or two at least, but there's no real way to know. You'll probably be fine anyway if you're not a high-value target. Most attacks today are done against a large batch of weak (and weakly protected) passwords, not a single strong one.

  How effective is doubling a passphrase? Like I have now [passphrase]
  and simply doule it: [passphrase][passphrase]. So I don't really have
  more stuff to remember, just more stuff to type. That might serve me
  for a time.

It doesn't really help all that much. You're not adding lots of uncertainty to the new passphrase, you just doubled it. Now that this question is on the public internet, an attacker trying to target you might try every combination of 5 words, and then double them and try again, just in case you doubled your passphrase. This means the attacker will have to work twice as hard to obtain your passphrase, not very useful. Adding a single Diceware-grade word is considerably more effective.

  Oh, another interesting question as well: let's say I use one exact
  password on many similar forum pages. Will this generate the exact
  same hashes if they use the same forum engine? I know, you can't
  recover the password from the hash, but they may find same hash = same
  guy, right?

It depends. In an ideal world.. no. The hash functions would be different, and they would use a random salt anyway. But, in the real world, yes, it's quite likely that many forums out there are still using MD5(password) and in that case, the same hash will end up in multiple databases, which is bad.

But if a forum engine is well-designed, that should not happen - each user will be given a random "salt" to differentiate his password from other users', this means if you create the same account on two different forums (even using the same forum code) you will most likely be given different salts, which'll make the two hashes differ.

  I don't really want to mess around with a Yubikey. Heck, I Googled it
  and didn't really managed to find out what it is, what it does. Maybe
  I'm not the target market. I'm just a simple user. Carrying around a
  Yubikey would also be a red flag in my eyes. He has secrets!

Everyone has secrets, and people carry around authenticators already, don't they? :) Basically, it's a two-factor authentication token. When you log into a website, you usually only use one-factor authentication: you know your password. But in a two-factor authentication process, you need to provide what you know (password, passphrase) and something else, either of:

what you are (biometric fingerprint, retina scan)
what you have (a physical object, such as a security token)


Double discrete logarithm on elliptic curve Background:

I am attempting to implement the paper Publicly Verifiable Secret Sharing. I managed to get it working using modular groups, but when I want to make it more efficient by transferring to elliptic curve groups, Section 3.1 in the paper gives me problems:

Let $p$ be a large prime.

$G$ is a group of order $p$

$g$ is a generator of $G$

$q = (p - 1)/2$ is prime.

$h$ $\epsilon$ $\Bbb Z_p^*$ is an element of order q.

The double discrete logarithm of $y$ to the bases $g$ and $h$ is defined as $x$ where:

$ y = g^{(h^x)} $

Question:

Implementing this double exponentiation is straightforward in modular groups since $h^x$ can be naturally interpreted as an integer. However, in the case of elliptic curves, $h^x$ is interpreted as the point $h$ added to itself $x$ times, resulting in curve point, $[x]h$. It is then unclear to me how to get $y = g^{(h^x)}$, knowing $g$, $h$ and $x$. To calculate a curve point to the power of another curve point does not seem possible to me.

The folklore is that any cryptographic scheme based on a modular multiplicative group can be translated to an additive curve group. However, I don't see how this case. Can this double exponentiation be done on an elliptic curve or is is only possible in modular groups?

However, in the case of elliptic curves, $h^x$ is interpreted as the point
  $h$ added to itself $x$ times, resulting in curve point, $[x]h$

That is incorrect; as you had stated previously:

  $h \in \mathbb{Z}_p^*$ is an element of order $q$.

That is, $h$ is not a point on the elliptic curve; instead, it is a member of a finite field, and so $h^x$ is interpreted as $h$ multiplied to itself $x$ times (using the field multiplication operation).

  The folklore is that any cryptographic scheme based on a modular multiplicative group can be translated to an additive curve group.

One has to be careful; there are schemes such as SRTP that really rely on a modular field (rather than a modular group).

However, even in those cases where things can translate nicely (which are actually most of them; exceptions are comparatively rare), you do have to remember that, while the actual group operation (modular multiplication) translates into point addition, the operations on the exponents (which are done modulo $p-1$ in the modular case) translate to integer operations modulo $q$ in the Elliptic Curve case.


Why standard deviation of BLISS is so high? In lattice based digital signature scheme BLISS why the standard deviation is so high (215) compared to the encryption schemes?

I am assuming you are asking why the standard deviation in BLISS is high compared to that of the errors in encryption schemes.  The answer is that the errors in encryption and the random variables with high standard deviation in BLISS (and other lattice signatures) play very different roles.  In encryption, one simply needs to generate an error $e$ such that $(a,as+e)$ looks random.  You don't need to have a high standard deviation at all for that.

In BLISS, the random variable $y$ that has a high standard deviation is used for masking the secret.  In particular, a part of the signature is an element $z=y+sc$ where $s$ is a part of the secret and $c$ is the challenge.  What is needed for security is that the distribution of $z$ is completely independent of $s$ -- this ensures that signatures do not leak the secret.  The best way we know of how to do that is generate $y$ according to a discrete gaussian distribution of standard deviation proportional to $\|sc\|$ and then do rejection sampling. That is why in BLISS the $\sigma$ is of size proportional to $\|sc\|$.


ECC Complexity order of point addition, scalar point multiplication and selecting random point I am facing this problem in calculating the order of a process which involves ECC point addition: $P+Q$ , scalar multiplication: $aP$, and selecting random points in the group. The group is of prime order say $q$.

What is the time complexity order of these operations? Is it $O(n)$, $O(log(n))$ or something different?

It depends on the multiplication algorithm used. Let $n$ be the bit size of the finite field used, and let $O(n^k)$ be the complexity of the multiplication algorithm used (e.g. $k=2$ for schoolbook multiplication, or $k=1.585$ for Karatsuba multiplication). Then:

Point addition: $O(n^k)$ (a constant number of multiplications)
Scalar multiplication: $O(n^{k+1})$
Selecting random point: depends on the method, but usually the same as scalar multiplication.

As pointed out by poncho, the point addition (and the scalar multiplication) can require a multiplication inverse, whose complexity again depends on the algorithm and may be larger than the complexity of multiplication. For example, binary euclidean takes $O(n^2)$, Fermat's little theorem takes $O(n^{k+1})$.


AES mode which verifies data integrity AFTER decryption I wonder if there is an AES mode which would verify data integrity after decryption operation.

Due to the reasons which does not matter here, there is a possibility that AES implementation I use may produce wrong results under certain conditions (particular data length, memory alignment etc). On the platform, two authenticated encryption modes are available: GCM and CCM.

There is an answer on Crypto which explains that CCM does MAC on plaintext whereas GCM does on cyphertext. Does it mean that if AES should malfunction during decryption, CCM will detect it whereas GCM won't?

Yes, you are correct, as long as it really only is the AES part which could dysfunction.

Quoting another source, for example Wikipedia's CCM page:

  These two primitives are applied in an "authenticate-then-encrypt"
  manner, that is, CBC-MAC is first computed on the message to obtain a
  tag t; the message and the tag are then encrypted using counter mode.

Note that we generally do not recommend to do "Mac then Encrypt", however CCM is a mode of encryption which features its very own proof of security, so you are good to go.


Motivation for frequent key updates I am wondering if there is any reason to regularly update cryptographic keys, that are used for authentication purposes in a real-time system.

A key should be updated if it is weak, broken, compromised, or leaked. Another valid reason would be a weak authentication scheme. For instance, CBS-MAC is prone to message forgery in case messages of different length are authenticated using the same key. AES-GCM with the same IV is careless if the same key is used.

As Swashbuckler pointed out, block ciphers leak information and therefore, encryption keys should be updated. With regard to authentication, I do not see such a reason, because there is no confidential data and even if the adversary observed a collision, he could not learn the key (in most cases).

Key updates, hence, do not give any benefit from a pure security point of view if a strong cryptosystem is deployed. Do I oversee something?

All block ciphers leak information.  No matter the mode used there is a limit on the amount of data that should be encrypted with a single key, irrespective of the number of different IVs used, in order to not leak too much information that an attacker might be able to determine some of the encrypted data.  For AES, it seems that the limit seems to be around 64 GB no matter the mode.

See the book Cryptography Engineering: Design Principles and Practical Applications and the paper The Missing Difference Problem, and its
Applications to Counter Mode Encryption.


Encryption(AES) and verification per message I want to send/receive messages with A (an peer) using TCP socket.
I want to encrypt messages using AES CBC.
Only I and A know a symmetric key K1 used in AES CBC, and K2 used in HMAC.
The size of each message is small( < 100 bytes).
Low latency is needed.
(verification per message is needed.)

Then, I want to verify if the messages are encrypted by A.

Idea 1:
Calculate HMAC of each message.
example: Messages = M1 HMAC(M1) M2 HMAC(M2) ....
         Send(AES_CBC(Messages))
Receiver decyprt Messages and checks if sent "HMAC(M1)" is the same as HMAC(sent "M1").

Idea 2:
Pad zero bits.
example: Messages = M1 Z1 M2 Z2 ....
         Send(AES_CBC(Messages))
Receiver decrypt Messages and check if Z1 is zero.

My question is "Are Idea 1 and 2 secure as assumed by length of bits?"
(example: I put 8bit HMAC or zeros, then I can't break verification the probability of larger than 1 / 256?)

Sorry for my poor English.
Thank you.

Idea 1 is similar to what TLS actually does (and begs the question "why aren't you using TLS?").  Modern thought is that it'd be generally better if you first encrypt, and then perform the MAC, as in:

E := AES(M)
Send IV, Encrypted HMAC(IV | Encrypted)

But no radical problem is known with your idea (unless you send M1 and M2 at different times; if you do, you open yourself up to a chosen plaintext attack -- however, that's an issue with CBC mode, not your general idea)
On the other hand, idea 2 is known to be broken; if the messages are longer than 32 bytes, then the attacker can (for example) modify one of the first bytes in the encrypted region that holds M1; on decryption, this would modify the first 32 bytes of M1, but nothing past that.  That is, the encrypted zeros would still decrypt as zero, and so the attacker has managed to modify M1 undetected.


Collusion resistant computing of same function by two servers Is there a secure way of computing same hash function of replicated data by two servers. I mean that both servers host the same version of replicated data and they should output h(M) without colluding, i.e., both of them really compute the specified function.

It sounds like what you really want is a Proof of Replication, where you can have multiple servers prove that they each have their own copy of a file.

The servers must each prove that they've been hosting their own redundant copy of file the whole time, and that they haven't just downloaded it just-in-time in order to create the proof. If you upload a file to a cloud service that claims they'll host N redundant copies of the file, they can use proofs of replication in order to confirm that they are in fact keeping N copies and not just one.

Protocol Labs (developer of IPFS and Filecoin) has developed a strategy for proofs of replication. Page 8 of the Filecoin Primer has a short description and diagram overviewing the strategy, and their Proof of Replication paper is more in-depth.

The basic idea is that each server is given a unique "sealed" replica of the data. The data may be easily recoverable from the sealed version. Creating (or recreating) the sealed version takes a predictable amount of time and may be done by anyone. The verifier can issue a challenge to a server that can only be answered by using that server's uniquely-sealed version of the data, and the verifier expects the server to answer within a timeout period that's shorter than the amount of time it would take for the server to download the data from another server and recreate the seal.


Performance bottlenecks in Paillier encryption I'm implementing Paillier encryption and I'd like some recommendations about improving its performance.

Firstly, I have to note the following:

I have already set g=1+n to get rid of one exponentiation.
I've been using the CRT to improve decryption.

Nevertheless, the computation of r^n mod n^2 is rather intensive, do you have any other trick to improve the performance?

Note: I don't want to use the Catalano et al. improvement with e as I want to keep its homomorphic property intact.

Recall that in Paillier encryption with public key $n$ of private factorization and $g=1+n$, encryption of plaintext $m$ reduces to:

choose random $r$, $0<r<n$
compute and output ciphertext $c=(1+n\cdot m)\cdot r^n\bmod n^2$.

Some ideas:

In some contexts, it is feasible to pre-compute $r^n\bmod n^2$ in masked time, before the encryption itself, meaning there is no modular exponentiation involved in encryption (only one multiplication and one modular multiplication); delay from plaintext-in to ciphertext-out is thus drastically reduced.
Using existing tightly optimized modular exponentiation code like in GMP might achieve 3, 4 and 5 below with little effort.
Tight coding (often, assembly) pays a lot for modular multiplication, and thus modular exponentiation (which is dominated by modular multiplication). Gaining a factor of 3 is common, 10 is not unseen if assembly coding allows to double the effective word width used for multiplication (e.g. C might not allows to use the full 128-bit result of a 64-bit times 64-bit multiplication available in hardware, or effective use of the carry bit).
Depending on hardware and size of $n$, it might pay to perform some optimizations that are not worthwhile for RSA and $n$ of comparable size, because the modulus width for modular multiplications is doubled in Paillier; even quadrupled (or more with multiprime-RSA) if the CRT is used and one compares the expensive operations, which are encryption in Paillier, and decryption in RSA. These optimizations include

sub-quadratic multiplication, like Karatsuba and friends;
modular reduction by multiplication with pre-computed inverse;
performing modular squaring by squaring with reuse of partial products (as in Algorithm 14.16 in the HAC) followed by modular reduction.

Sliding Window exponentiation (see Algorithm 14.85 in the HAC) will give some improvement (like -20%) over a standard exponent scanning, and slightly more so than in RSA.


How is it possible to parallelize a hashing function to crack an iteratively hashed password? Suppose I have an algorithm that relies on multiple iterations of a hash function like SHA1 to slow down an attacker trying to bruteforce a hash.

digest[0] = hash(password + salt)
for i in 1..r:
    digest[i] = hash(digest[i-1] + password)

The final digest[r] is then used as the hash. How does this compare to a more standard implementation like PBKDF2 or bcrypt?

This website states:

  simply iteratively hashing the hash of the password isn't enough as it can be parallelized in hardware and executed as fast as a normal hash.

Is there any truth to this statement? Since every iteration of the hash function is dependent on the previous, how could this be possible?

The bit about parallelization is not for hashing one password. But the attacker, by definition, has a lot of passwords to try, and these can be computed in parallel, provided that the function maps well to whatever parallel architecture the attacker would like to use. In the case of the multi-SHA-1 method you describe, it maps very well on GPU. Note that the same can be said about PBKDF2, which is why I tend to recommend bcrypt, which is more resilient to GPU.

Although I do not immediately see any obvious problem with your SHA-1* function, it has the generic issue of being homemade and of not having been investigated thoroughly by dozens of cryptographers during several years. Therefore I would not trust it.