Difference between revisions of "Np1sec/algebraic"
m (Dmitri moved page MpOTR/algebraic to Np1sec/algebraic)
 
(9 intermediate revisions by one other user not shown)
Line 31: Line 31:
 
|-
 
|-
 
|align="right"| Receive other users' id/key
 
|align="right"| Receive other users' id/key
−
|align="center"|<math>plist_i|klist_i \leftarrow (U_1|y_1|\dots|U_n|y_n)</math>
+
|align="center"|<math>plist_i|klist_i \leftarrow (U_1|y_1|\dots|U_n|y_n)\cup(U_i,y_i)</math>
 
|-
 
|-
 
|align="right"|Compute Session Id
 
|align="right"|Compute Session Id
Line 52: Line 52:
 
|-
 
|-
 
|align="right"|Broadcast key shares and confirmation
 
|align="right"|Broadcast key shares and confirmation
−
|align="center"|<math>(U_i, z_i, \sigma_i kc_i)</math>
+
|align="center"|<math>(U_i, z_i, \sigma_i, kc_i)</math>
 
|-
 
|-
 
|align="right"| Receive other users' key shares and confirmation
 
|align="right"| Receive other users' key shares and confirmation
Line 58: Line 58:
 
|-
 
|-
 
|align="right"|Check validity of key confirmation
 
|align="right"|Check validity of key confirmation
−
|align="center"|<math>kc_i[j] == kc_j[i] \textrm{ for } j \in \{1,\dots,n\}</math>
+
|align="center"|<math>kc_i[j] == H(k_{j,i}, U_j) \textrm{ for } j \in \{1,\dots,n\}</math>
 
|-
 
|-
 
|align="right"|Check public shares
 
|align="right"|Check public shares
Line 73: Line 73:
 
|-
 
|-
 
|align="right"|Broadcast session key confirmation
 
|align="right"|Broadcast session key confirmation
−
|align="center"|<math>k_i \leftarrow H(k_i, sid_i, U_i)</math>
+
|align="center"|<math>skc_i \leftarrow H(k_i, sid_i, U_i)</math>
 
|}
 
|}
  
Line 82: Line 82:
 
!align="center"|Pseudo-code
 
!align="center"|Pseudo-code
 
|-
 
|-
−
|align="right"| broadcast all user's identities (U_1|y_1|\dots|U_n|y_n)
+
|align="right"| broadcast all user's identities  
−
|align="center"|<math> x_i \leftarrow [0, order(g)]</math>
+
|align="center"|<math> (U_1|y_1|\dots|U_n|y_n) </math>
 
|-
 
|-
 
|align="right"| Receive other users' id/key and update participant list
 
|align="right"| Receive other users' id/key and update participant list
−
|align="center"|<math>plist_i|klist_i \textrm{append} (U_j|y_j)</math>
+
|align="center"|<math>(plist_i|klist_i) \cup (U_j|y_j)</math>
−
|-
+
−
|align="right"|Broadcast User identity and the DH key
+
−
|align="center"|<math>(U_i, y_i)</math>
+
−
|-
+
−
|align="right"| Receive other users' id/key
+
−
|align="center"|<math>plist_i|klist_i \leftarrow (U_j|y_j|\dots|U_j|y_j)</math>
+
 
|-
 
|-
 
|align="right"|Compute Session Id
 
|align="right"|Compute Session Id
Line 98: Line 92:
 
|-
 
|-
 
|align="right"|Generate Triple Diffie-Hellman P2P key for the new participant
 
|align="right"|Generate Triple Diffie-Hellman P2P key for the new participant
−
|align="center"|<math>k_{i,j} \leftarrow H({y_j}^{lp_i},LP_j^{x_i},y_j^{x_i})</math>}}
+
|align="center"|<math>k_{i,j} \leftarrow H({y_j}^{lp_i},LP_j^{x_i},y_j^{x_i})</math>
 
|-
 
|-
 
|align="right"|Generate key confirmations
 
|align="right"|Generate key confirmations
−
|align="center"|<math>kc_i \leftarrow (H(k_{i,j}, U_j)</math>
+
|align="center"|<math>kc_{i,j}\leftarrow H(k_{i,j}, U_i) </math>
 
|-
 
|-
 
|align="right"|Generate secret shares
 
|align="right"|Generate secret shares
Line 116: Line 110:
 
|-
 
|-
 
|align="right"| Receive other users' key shares and new users confirmation
 
|align="right"| Receive other users' key shares and new users confirmation
−
|align="center"|<math>(U_1|z_1,\sigma_1,\dots U_n|z_n,\sigma_n), kc_{ij}</math>
+
|align="center"|<math>(U_1|z_1,\sigma_1,\dots U_n|z_n,\sigma_n), kc_{i,j}</math>
 
|-
 
|-
 
|align="right"|Check validity of key confirmation
 
|align="right"|Check validity of key confirmation
−
|align="center"|<math>kc_i[j] == kc_j[i]</math>
+
|align="center"|<math>kc_{j,i} == H(k_{i,j},U_j)</math>
 
|-
 
|-
 
|align="right"|Check public shares
 
|align="right"|Check public shares
Line 134: Line 128:
 
|-
 
|-
 
|align="right"|Broadcast session key confirmation
 
|align="right"|Broadcast session key confirmation
−
|align="center"|<math>k_i \leftarrow H(k_i, sid_i, U_i)</math>
+
|align="center"|<math>skc_i \leftarrow H(k_i, sid_i, U_i)</math>
 
|}
 
|}
  
Line 143: Line 137:
 
|-
 
|-
 
|align="right"| Remove leaving user's id/key and update participant list
 
|align="right"| Remove leaving user's id/key and update participant list
−
|align="center"|<math>plist_i|klist_i \textrm{remove} (U_j|y_j)</math>
+
|align="center"|<math>(plist_i|klist_i) \backslash (U_j|y_j)</math>
 
|-
 
|-
 
|align="right"|Compute Session Id
 
|align="right"|Compute Session Id
 
|align="center"|<math>sid_i \leftarrow H(U_1|y_1|\dots|U_n|y_n)</math>
 
|align="center"|<math>sid_i \leftarrow H(U_1|y_1|\dots|U_n|y_n)</math>
−
|-
 
−
|align="right"|Generate key confirmations
 
−
|align="center"|<math>kc_i \leftarrow (H(k_{i,j}, U_j)</math>
 
 
|-
 
|-
 
|align="right"|Generate secret shares
 
|align="right"|Generate secret shares
Line 161: Line 152:
 
|-
 
|-
 
|align="right"|Broadcast key shares
 
|align="right"|Broadcast key shares
−
|align="center"|<math>(U_i, z_i, \sigma_i,>kc_i</math>}}<math>)</math>
+
|align="center"|<math>(U_i, z_i, \sigma_i)</math>
 
|-
 
|-
 
|align="right"| Receive other users' key shares
 
|align="right"| Receive other users' key shares
−
|align="center"|<math>(U_1|z_1,\sigma_1,\dots U_n|z_n,\sigma_n)
+
|align="center"|<math>(U_1|z_1,\sigma_1,\dots U_n|z_n,\sigma_n)</math>
−
|-
+
−
|align="right"|Check validity of key confirmation
+
−
|align="center"|<math>kc_i[j] == kc_j[i]</math>
+
 
|-
 
|-
 
|align="right"|Check public shares
 
|align="right"|Check public shares
Line 184: Line 172:
 
|align="center"|<math>skc_i \leftarrow H(k_i, sid_i, U_i)</math>
 
|align="center"|<math>skc_i \leftarrow H(k_i, sid_i, U_i)</math>
 
|}
 
|}
−
 
  
 
==Send==
 
==Send==
Line 195: Line 182:
 
|-
 
|-
 
|align="right"| Append the hash of the session digest up to parent of current message   
 
|align="right"| Append the hash of the session digest up to parent of current message   
−
|align="center"|<math> m \leftarrow (m, Digest(parnet(m)), parent\_id) </math>
+
|align="center"|<math> m \leftarrow (m, Digest(parent(m)), parent\_id) </math>
 
|-
 
|-
 
|align="right"| Sign the message
 
|align="right"| Sign the message
Line 201: Line 188:
 
|-
 
|-
 
|align="right"|Encrypt
 
|align="right"|Encrypt
−
|align="center"|<math>e \leftarrow Enc_k_{sid}(m)</math>
+
|align="center"|<math>e \leftarrow Enc_{k_{sid}}(m)</math>
 
|-
 
|-
 
|align="right"| Broadcast the message
 
|align="right"| Broadcast the message
Line 213: Line 200:
 
|-
 
|-
 
|align="right"| check signature
 
|align="right"| check signature
−
|align="center"|<math> verify(m) == (m, \sigma) </math>
+
|align="center"|<math> verify(m,\sigma) </math>
 +
|-
 +
|align="right"| update message block chain
 +
|align="center"|<math> Insert(BlackChain_{sid}, m) </math>
 
|-
 
|-
 
|align="right"| decrypt messagen
 
|align="right"| decrypt messagen
Line 219: Line 209:
 
|-
 
|-
 
|align="right"| Verify session id and hash
 
|align="right"| Verify session id and hash
−
|align="center"|<math>\sigma \leftarrow sid_i == sid_{rec} & h == Digest(parent\_id)</math>
+
|align="center"|<math> sid_i == sid_{rec} \;  \textrm{and}  \; h == Digest(parent\_id)</math>
 
|-
 
|-
−
|align="right"| Update key share or session key
+
|align="right"| Update sender key or share key
−
|align="center"|<math>(y_j,z_{ji})</math>
+
|align="center"|<math>y_j \leftarrow s \; \textrm {  or  } \; z_{j} \leftarrow s</math>
 +
|-
 +
|align="right"| if all users' share are received session key
 +
|align="center"|<math>k_i \leftarrow ComputeSessionKey(z_1,...,z_n) </math>
 
|-
 
|-
 
|align="right"| return m
 
|align="right"| return m
 
|align="center"|<math>m</math>
 
|align="center"|<math>m</math>
 
|}
 
|}
 +
 +
[[Category: mpOTR]]

Latest revision as of 18:46, 2 December 2014

Chatroom Setup

Description Pseudo-code
Generate ephemeral DH private key of the room initiator x_{i}\leftarrow [0,order(g)]
Generate DH key for BD, Triple DH and Signature y_{i}\leftarrow g^{{x_{i}}}
Set participant list plist\leftarrow [U_{i}]

Join

Description Pseudo-code
Generate ephemeral DH private key x_{i}\leftarrow [0,order(g)]
Generate DH key for BD, Triple DH and Signature y_{i}\leftarrow g^{{x_{i}}}
Broadcast User identity and the DH key (U_{i},y_{i})
Receive other users' id/key plist_{i}|klist_{i}\leftarrow (U_{1}|y_{1}|\dots |U_{n}|y_{n})\cup (U_{i},y_{i})
Compute Session Id sid_{i}\leftarrow H(U_{1}|y_{1}|\dots |U_{n}|y_{n})
Generate Triple Diffie-Hellman P2P keys k_{{i,j}}\leftarrow H({y_{j}}^{{lp_{i}}},LP_{j}^{{x_{i}}},y_{j}^{{x_{i}}})}}
Generate key confirmations kc_{i}\leftarrow (H(k_{{i,1}},U_{1}),\dots ,H(k_{{i,n}},U_{n}))}}
Generate secret shares z'_{{i,l}}\leftarrow H(k_{{i,i-1}},sid_{i}),z'_{{i,r}}\leftarrow H(k_{{i,i+1}},sid_{i})
Generate public shares z_{i}\leftarrow z'_{{i,l}}\oplus z'_{{i,r}}
Sign identity, shares \sigma _{i}\leftarrow Sign_{{x_{i}}}(U_{i},z_{i},sid)
Broadcast key shares and confirmation (U_{i},z_{i},\sigma _{i},kc_{i})
Receive other users' key shares and confirmation (U_{1}|z_{1},\sigma _{1},kc_{{1i}},\dots U_{n}|z_{n},\sigma _{n},kc_{{ni}})
Check validity of key confirmation kc_{i}[j]==H(k_{{j,i}},U_{j}){\textrm {for}}j\in \{1,\dots ,n\}
Check public shares z_{1}\oplus \dots \oplus z_{n}==0
Check signatures verify_{{y_{i}}}(\sigma _{j}){\textrm {for}}j\in \{1,\dots ,n\}
Recover secret shares z'_{{j,r}}\leftarrow z'_{{j-1,r}}\oplus z_{j}
Generate session key k_{i}\leftarrow H(z'_{{1,r}}\dots z'_{{n,r}},sid_{i})
Broadcast session key confirmation skc_{i}\leftarrow H(k_{i},sid_{i},U_{i})

Accept

Description Pseudo-code
broadcast all user's identities (U_{1}|y_{1}|\dots |U_{n}|y_{n})
Receive other users' id/key and update participant list (plist_{i}|klist_{i})\cup (U_{j}|y_{j})
Compute Session Id sid_{i}\leftarrow H(U_{1}|y_{1}|\dots |U_{n}|y_{n})
Generate Triple Diffie-Hellman P2P key for the new participant k_{{i,j}}\leftarrow H({y_{j}}^{{lp_{i}}},LP_{j}^{{x_{i}}},y_{j}^{{x_{i}}})
Generate key confirmations kc_{{i,j}}\leftarrow H(k_{{i,j}},U_{i})
Generate secret shares z'_{{i,l}}\leftarrow H(k_{{i,i-1}},sid_{i}),z'_{{i,r}}\leftarrow H(k_{{i,i+1}},sid_{i})
Generate public shares z_{i}\leftarrow z'_{{i,l}}\oplus z'_{{i,r}}
Sign identity, shares \sigma _{i}\leftarrow Sign_{{x_{i}}}(U_{i},z_{i},sid)
Broadcast key shares and confirmation (U_{i},z_{i},\sigma _{i},kc_{i})
Receive other users' key shares and new users confirmation (U_{1}|z_{1},\sigma _{1},\dots U_{n}|z_{n},\sigma _{n}),kc_{{i,j}}
Check validity of key confirmation kc_{{j,i}}==H(k_{{i,j}},U_{j})
Check public shares z_{1}\oplus \dots \oplus z_{n}==0
Check signatures verify_{{y_{i}}}(\sigma _{j}){\textrm {for}}j\in \{1,\dots ,n\}
Recover secret shares z'_{{j,r}}\leftarrow z'_{{j-1,r}}\oplus z_{j}
Generate session key k_{i}\leftarrow H(z'_{{1,r}}\dots z'_{{n,r}},sid_{i})
Broadcast session key confirmation skc_{i}\leftarrow H(k_{i},sid_{i},U_{i})

Leave

Description Pseudo-code
Remove leaving user's id/key and update participant list (plist_{i}|klist_{i})\backslash (U_{j}|y_{j})
Compute Session Id sid_{i}\leftarrow H(U_{1}|y_{1}|\dots |U_{n}|y_{n})
Generate secret shares z'_{{i,l}}\leftarrow H(k_{{i,i-1}},sid_{i}),z'_{{i,r}}\leftarrow H(k_{{i,i+1}},sid_{i})
Generate public shares z_{i}\leftarrow z'_{{i,l}}\oplus z'_{{i,r}}
Sign identity, shares \sigma _{i}\leftarrow Sign_{{x_{i}}}(U_{i},z_{i},sid)
Broadcast key shares (U_{i},z_{i},\sigma _{i})
Receive other users' key shares (U_{1}|z_{1},\sigma _{1},\dots U_{n}|z_{n},\sigma _{n})
Check public shares z_{1}\oplus \dots \oplus z_{n}==0
Check signatures verify_{{y_{i}}}(\sigma _{j}){\textrm {for}}j\in \{1,\dots ,n\}
Recover secret shares z'_{{j,r}}\leftarrow z'_{{j-1,r}}\oplus z_{j}
Generate session key k_{i}\leftarrow H(z'_{{1,r}}\dots z'_{{n,r}},sid_{i})
Broadcast session key confirmation skc_{i}\leftarrow H(k_{i},sid_{i},U_{i})

Send

Description Pseudo-code
Generate new DH Key or new key share if needed and append m\leftarrow (sid,s,m)
Append the hash of the session digest up to parent of current message m\leftarrow (m,Digest(parent(m)),parent\_id)
Sign the message \sigma \leftarrow Sign_{{x_{i}}}(m)
Encrypt e\leftarrow Enc_{{k_{{sid}}}}(m)
Broadcast the message (sid_{i},e,\sigma )

Receive

Description Pseudo-code
check signature verify(m,\sigma )
update message block chain Insert(BlackChain_{{sid}},m)
decrypt messagen sid_{{rec}},s,m,h,parent\_id\leftarrow Dec_{k}(m)
Verify session id and hash sid_{i}==sid_{{rec}}\;{\textrm {and}}\;h==Digest(parent\_id)
Update sender key or share key y_{j}\leftarrow s\;{\textrm {or}}\;z_{{j}}\leftarrow s
if all users' share are received session key k_{i}\leftarrow ComputeSessionKey(z_{1},...,z_{n})
return m m
Retrieved from "https://learn.equalit.ie/mw/index.php?title=Np1sec/algebraic&oldid=1558"