Refactoring HMAC checks, replacing de type checks with IsKV, IsCR, IsSS, and IsQS
authorrtrimana <rtrimana@uci.edu>
Mon, 22 Aug 2016 19:13:22 +0000 (12:13 -0700)
committerrtrimana <rtrimana@uci.edu>
Mon, 22 Aug 2016 19:13:22 +0000 (12:13 -0700)
doc/iotcloud.tex

index fd8a719..9d970c4 100644 (file)
@@ -182,7 +182,6 @@ $SlotVal(slot_s = \tuple{s, sv})=sv$ \\
 \subsection{Client Algorithm}\r
 \subsubsection{Reading Slots}\r
 \textbf{Data Entry} \\\r
-$de$ is a data entry \\\r
 $k$ is key of entry \\\r
 $v$ is value of entry \\\r
 $kv$ is a key-value entry $\tuple{k,v}$, $kv \in DE$ \\\r
@@ -191,11 +190,14 @@ id + last s of a machine, $ss \in DE$ \\
 $qs$ is a queue state entry (contains $max$ size of queue), $qs \in DE$ \\\r
 $cr$ is a collision resolution entry $\tuple{s_{col},id_{col}}$, \r
 s + id of a machine that wins a collision, $cr \in DE$ \\\r
+$de$ is a data entry that can be a $kv$, $ss$, $qs$, or $cr$ \\\r
 $DE$ is a set of all data entries, possibly of different types, in a single message \\\r
 $s \in SN$ is a sequence number \\\r
 $id$ is a machine ID\\\r
 $hmac_p$ is the HMAC value of the previous slot \\\r
 $hmac_c$ is the HMAC value of the current slot \\\r
+$hmac_{p_g}$ is the HMAC value of the previous slot in procedure $\Call{ProcessSL}{}$ \\\r
+$hmac_{c_g}$ is the HMAC value of the current slot in procedure $\Call{ProcessSL}{}$ \\\r
 $Dat_s = \tuple{s,id,hmac_p,DE,hmac_c}$ \\\r
 $slot_s = \tuple{s, E(Dat_s)} = \r
 \tuple{s, E(\tuple{s,id,hmac_p,DE,hmac_c})}$ \\ \\\r
@@ -242,14 +244,23 @@ $GetLivEntLastS(LV_s,kv_s)= s$ \textit{such that} $\tuple{kv, s} \in LV_s
        \wedge \forall \tuple{kv_s, s_s} \in LV_s, kv_s = kv$ \\\r
 $GetKV($key-value data entry$)=\tuple{k_s,v_s} = kv_s$ \\\r
 $GetSS($slot-sequence data entry$)=\tuple{id_s,s_{s_{last}}} = ss_s$ \\\r
-$GetQS($queue-state data entry$)=qs_s$ \\\r
-$GetCR($collision-resolution data entry$)=\tuple{s_s,id_s} = cr_s$ \\\r
-$GetKey(kv = \tuple{k, v})=k$ \\\r
-$GetVal(kv = \tuple{k, v})=v$ \\\r
-$GetId(ss = \tuple{id, s_{last}})=id$ \\\r
-$GetSLast(ss = \tuple{id, s_{last}})=s_{last}$ \\\r
-$GetS(cr = \tuple{s, id})=s$ \\\r
-$GetId(cr = \tuple{s, id})=id$ \\\r
+%$GetQS($queue-state data entry$)=qs_s$ \\\r
+$GetCR($de$)=\tuple{s_s,id_s} = cr_s$ \\\r
+$Hmac(Dat_s,SK) = hmac_c$ \textit{value computed from $s$, $id$,\r
+$hmac_p$, and $DE$ taken from $Dat_s$} \\\r
+$IsKV(de) = true$ \textit{if $de$ is a $kv$, false otherwise} \\\r
+$IsSS(de) = true$ \textit{if $de$ is a $ss$, false otherwise} \\\r
+$IsQS(de) = true$ \textit{if $de$ is a $qs$, false otherwise} \\\r
+$IsCR(de) = true$ \textit{if $de$ is a $cr$, false otherwise} \\\r
+$GetKey(kv)=k$\Comment{$kv = \tuple{k, v}$} \\\r
+$GetVal(kv)=v$ \\\r
+$GetId(ss)=id$\Comment{$ss = \tuple{id, s_{last}}$} \\\r
+$GetSLast(ss)=s_{last}$ \\\r
+$GetS(cr)=s$\Comment{$cr = \tuple{s, id}$} \\\r
+$GetId(cr)=id$ \\\r
+$GetLastS(sl_{last})=s$\Comment{$sl_{last} = \tuple{s,sv,id}$} \\\r
+$GetSV(sl_{last})=sv$ \\\r
+$GetID(sl_{last})=id$ \\\r
 $GetKeyVal(DT_s,k_s)= \tuple{k, v}$ \textit{such that} $\tuple{k, v} \r
        \in DT_s \wedge \forall \tuple{k_s, v_s} \in DT_s, k = k_s$ \\\r
 $MaxLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \r
@@ -270,10 +281,10 @@ $MaxSMSeqN(SM_s)= s$ \textit{such that} $\tuple{s, id} \in SM_s
 \r
 \begin{algorithmic}[1]\r
 \Function{GetQueSta}{$DE_s$}\r
-\State $de_{qs} \gets ss$ \textit{such that} $ss \in DE_s, \r
-       de_s \in D \land type(de_s) = ``qs"$\r
-\If{$de_{qs} \neq \emptyset$}\r
-       \State $qs_{ret} \gets GetQS(de_{qs})$\r
+\State $qs_{de} \gets qs$ \textit{such that} $qs \in DE_s, \r
+       de_s \in D \land IsQS(de_s)$\r
+\If{$qs_{de} \neq \emptyset$}\r
+       \State $qs_{ret} \gets qs_{de})$\r
 \Else\r
        \State $qs_{ret} \gets \emptyset$\r
 \EndIf\r
@@ -283,14 +294,14 @@ $MaxSMSeqN(SM_s)= s$ \textit{such that} $\tuple{s, id} \in SM_s
 \r
 \begin{algorithmic}[1]\r
 \Function{GetSlotSeq}{$DE_s$}\r
-\State $DE_{ss} \gets \{de | de \in DE_s \land type(de) = ``ss"\}$\r
+\State $DE_{ss} \gets \{de | de \in DE_s \land IsSS(de)\}$\r
 \State \Return{$DE_{ss}$}\r
 \EndFunction\r
 \end{algorithmic}\r
 \r
 \begin{algorithmic}[1]\r
 \Function{GetColRes}{$DE_s$}\r
-\State $DE_{cr} \gets \{de | de \in DE_s \land type(de) = ``cr"\}$\r
+\State $DE_{cr} \gets \{de | de \in DE_s \land IsCR(de)\}$\r
 \State \Return{$DE_{cr}$}\r
 \EndFunction\r
 \end{algorithmic}\r
@@ -446,10 +457,27 @@ $MaxSMSeqN(SM_s)= s$ \textit{such that} $\tuple{s, id} \in SM_s
 \EndFunction\r
 \end{algorithmic}\r
 \r
+\begin{algorithmic}[1]\r
+\Function{ValidateHmacChain}{$Dat_s,s_s,hmac_{p_s},sl_l$}\r
+       \State $hmac_{p_{stored}} \gets GetPrevHmac(Dat_s)$\r
+       \If {$ \neg(s_s = 0 \land hmac_{p_s} = 0)$}\r
+               \State $s_l \gets GetLastS(sl_l)$\r
+               \If {$(s_s > s_l + 1) \land (hmac_{p_{stored}} \neq hmac_{p_s})$}\r
+                       \State \Call{Error}{'Invalid previous HMAC value'}\r
+               \EndIf\r
+       \EndIf\r
+       \If{$Hmac(Dat_s,SK) \neq GetCurrHmac(Dat_s)$ }\r
+               \State \Call{Error}{'Invalid current HMAC value'}\r
+       \EndIf\r
+       \State $hmac_{p_s} \gets Hmac(Dat_s,SK)$\Comment{Update $hmac_{p_s}$ for next check}\r
+\State \Return{$hmac_{p_s}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
 \begin{algorithmic}[1]\r
 \Function{UpdateDT}{$DT_s,DE_s,LV_s,s_s$}\r
-\State $DE_{s_{kv}} \gets \{de_s | de_s \in DE_s, type(de_s) = ``kv"\}$\r
-\ForAll{$de_s \in DE_s$}\r
+\State $DE_{s_{kv}} \gets \{de_s | de_s \in DE_s \land IsKV(de_s)\}$\r
+\ForAll{$de_s \in DE_{s_{kv}}$}\r
        \State $kv_s \gets GetKV(de_s)$\r
        \State $LV_s \gets \Call{UpdateKVLivEnt}{LV_s,kv_s,s_s}$\r
        \State $k_s \gets GetKey(kv_s)$\r
@@ -481,22 +509,24 @@ $MaxSMSeqN(SM_s)= s$ \textit{such that} $\tuple{s, id} \in SM_s
     \If{$s_g \neq s_{g_{in}}$}\r
                \State \Call{Error}{'Invalid sequence number'}\r
        \EndIf\r
+       \State $hmac_{p_g} \gets \Call{ValidateHmacChain}{Dat_g,s_g,hmac_{p_g},sl_{last}}$\r
+\r
+%      \State $hmac_{p_{stored}} \gets GetPrevHmac(Dat_g)$\r
+%      \If {$ \neg(s_g = 0 \land hmac_{p_g} = 0) \land hmac_{p_{stored}} \neq hmac_{p_g}$}\r
+%              \State \Call{Error}{'Invalid previous HMAC value'}\r
+%      \EndIf\r
+%      \If{$Hmac(Dat_g,SK) \neq GetCurrHmac(Dat_g)$ }\r
+%              \State \Call{Error}{'Invalid current HMAC value'}\r
+%      \EndIf\r
+%      \State $hmac_{p_g} \gets Hmac(Dat_g,SK)$\Comment{Update $hmac_{p_g}$ for next check}\r
+\r
        \State $DE_g \gets GetDatEnt(Dat_g)$\r
-       \State $hmac_{p_{stored}} \gets GetPrevHmac(Dat_g)$\r
-       \If {$ \neg(s_g = 0 \land hmac_{p_g} = 0) \land hmac_{p_{stored}} \neq hmac_{p_g}$}\r
-               \State \Call{Error}{'Invalid previous HMAC value'}\r
-       \EndIf\r
-       \If{$\Call{Hmac}{DE_g,SK} \neq GetCurrHmac(Dat_g)$ }\r
-               \State \Call{Error}{'Invalid current HMAC value'}\r
-       \EndIf\r
-       \State $hmac_{p_g} \gets Hmac(DE_g,SK)$\Comment{Update $hmac_{p_g}$ for next check}\r
        \State $qs_g \gets \Call{GetQueSta}{DE_g}$\Comment{Handle qs}\r
        \If{$qs_g \neq \emptyset \land qs_g > max_g$}\r
                \State $max_g \gets qs_g$\r
        \EndIf\r
     %Check for last s in Dat\r
-       \State $id_g \gets GetMacId(Dat_g)$\Comment{Handle last s}\r
-       \State $MS_g \gets \Call{UpdateLastSeqN}{id_g,s_g,MS_g}$\r
+       \State $MS_g \gets \Call{UpdateLastSeqN}{id_g,s_g,MS_g}$\Comment{Handle last s}\r
     %Check for last s in DE in Dat\r
        \State $DE_{g_{ss}} \gets \Call{GetSlotSeq}{DE_g}$\Comment{Handle ss}\r
        \If{$DE_{g_{ss}} \neq \emptyset$}\r
@@ -555,9 +585,11 @@ $MaxSMSeqN(SM_s)= s$ \textit{such that} $\tuple{s, id} \in SM_s
 \textit{$cs_g$ = counter of $ss \in SS$ for getting pairs (initially 0)} \\\r
 \textit{$cc_p$ = counter of $cr \in CR$ for putting pairs (initially 0)} \\\r
 \textit{$cc_g$ = counter of $cr \in CR$ for getting pairs (initially 0)} \\\r
-\textit{$hmac_{c_p}$ = the HMAC value of the current slot} \\\r
+\textit{$hmac_{c_p}$ = the HMAC value of the current slot in procedure \r
+$\Call{PutDataEntries}{}$} \\\r
 \textit{$hmac_{p_p}$ = the HMAC value of the previous slot \r
-($hmac_{p_p} = \emptyset$ for the first slot)} \\\r
+($hmac_{p_p} = \emptyset$ for the first slot) in procedure \r
+$\Call{PutDataEntries}{}$} \\\r
 \textit{$id_{self}$ = machine Id of this client} \\\r
 \textit{$sl_{last}$ = info of last slot in queue = \r
        $\tuple{s_{last},sv_{last},id_{last}}$ (initially $\emptyset$)} \\\r
@@ -575,9 +607,6 @@ $CreateSS(id_s,s_{s_{last}})=\tuple{id_s,s_{s_{last}}} = ss_s$ \\
 $CreateQS(max'_s)=qs_s$ \\\r
 $CreateCR(s_s,id_s)=\tuple{s_s,id_s} = cr_s$ \\\r
 $Encrypt(Dat_s,SK_s)=sv_s$ \\\r
-$GetLastS(sl = \tuple{s,sv,id})=s$ \\\r
-$GetSV(sl = \tuple{s,sv,id})=sv$ \\\r
-$GetID(sl = \tuple{s,sv,id})=id$ \\\r
 $GetColSeqN(SL_s,s_s)= \tuple{s, sv}$ \textit{such that} $\tuple{s, sv}\r
 \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s = s_s$ \\\r
 $GetKVPair(KV_s,k_s)= \tuple{ck,\tuple{k, v}}$ \textit{such that} \r