logo

SCIENCE CHINA Information Sciences, Volume 64 , Issue 8 : 182314(2021) https://doi.org/10.1007/s11432-020-3039-x

Cetus: an efficient symmetric searchable encryption against file-injection attack with SGX

More info
  • ReceivedApr 2, 2020
  • AcceptedAug 7, 2020
  • PublishedJul 9, 2021

Abstract


Acknowledgment

This work was supported by the National Natural Science Foundation of China (Grant No. 61672300), National Natural Science Foundation of Tianjin (Grant No. 18ZXZNGX00140), and National Natural Science Foundation for Outstanding Youth Foundation (Grant No. 61722203).


References

[1] Stefanov E, Van Dijk M, Shi E, et al. Path ORAM: an extremely simple oblivious RAM protocol. In: Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security. 2013. 299--310. Google Scholar

[2] Garg S, Mohassel P, Papamanthou C. TWORAM: efficient oblivious RAM in two rounds with applications to searchable encryption. In: Proceedings of Annual International Cryptology Conference. Berlin: Springer, 2016. 563--592. Google Scholar

[3] Naveed M, Prabhakaran M, Gunter C A. Dynamic searchable encryption via blind storage. In: Proceedings of 2014 IEEE Symposium on Security and Privacy, 2014. 639--654. Google Scholar

[4] Song X, Dong C, Yuan D. Forward Private Searchable Symmetric Encryption with Optimized I/O Efficiency. IEEE Trans Dependable Secure Comput, 2020, 17: 912-927 CrossRef Google Scholar

[5] Kim K S, Kim M, Lee D, et al. Forward secure dynamic searchable symmetric encryption with efficient updates. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017. 1449--1463. Google Scholar

[6] Liu Z, Lv S, Wei Y, et al. FFSSE: Flexible Forward Secure Searchable Encryption with Efficient Performance. IACR Cryptology ePrint Archive, 2017, 2017: 1105. Google Scholar

[7] Ghareh C J, Papadopoulos D, Papamanthou C, et al. New constructions for forward and backward private symmetric searchable encryption. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, 2018. 1038--1055. Google Scholar

[8] Bost R, Minaud B, Ohrimenko O. Forward and backward private searchable encryption from constrained cryptographic primitives. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017. 1465--1482. Google Scholar

[9] Etemad M, Küp?ü A, Papamanthou C. Efficient Dynamic Searchable Encryption with Forward Privacy. Proc Privacy Enhancing Technologies, 2018, 2018(1): 5-20 CrossRef Google Scholar

[10] Li J, Huang Y, Wei Y. Searchable Symmetric Encryption with Forward Search Privacy. IEEE Trans Dependable Secure Comput, 2019, : 1-1 CrossRef Google Scholar

[11] Bost R. $\Sigma$o$\phi$o$\varsigma$: forward secure searchable encryption. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016. 1143--1154. Google Scholar

[12] Cash D, Grubbs P, Perry J, et al. Leakage-abuse attacks against searchable encryption. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, 2015. 668--679. Google Scholar

[13] Stefanov E, Papamanthou C, Shi E. Practical dynamic searchable encryption with small leakage. In: Proceedings of Network and Distributed System Security Symposium, 2014. 71: 72--75. Google Scholar

[14] Song D X, Wagner D, Perrig A. Practical techniques for searches on encrypted data. In: Proceedings of 2000 IEEE Symposium on Security and Privacy, 2000. 44--55. Google Scholar

[15] Curtmola R, Garay J, Kamara S. Searchable symmetric encryption: Improved definitions and efficient constructions. JCS, 2011, 19: 895-934 CrossRef Google Scholar

[16] Chase M, Kamara S. Structured encryption and controlled disclosure. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2010. 577--594. Google Scholar

[17] Kamara S, Papamanthou C, Roeder T. Dynamic searchable symmetric encryption. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security, 2012. 965--976. Google Scholar

[18] Kamara S, Papamanthou C. Parallel and dynamic searchable symmetric encryption. In: Proceedings of International Conference on Financial Cryptography and Data Security. Berlin: Springer, 2013. 258--274. Google Scholar

[19] Cash D, Jaeger J, Jarecki S, et al. Dynamic searchable encryption in very-large databases: data structures and implementation. In: Proceedings of Network and Distributed System Security Symposium, 2014. 14: 23--26. Google Scholar

[20] Chang Y C, Mitzenmacher M. Privacy preserving keyword searches on remote encrypted data. In: Proceedings of International Conference on Applied Cryptography and Network Security. Berlin: Springer, 2005. 442--455. Google Scholar

[21] Hahn F, Kerschbaum F. Searchable encryption with secure and efficient updates. In: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, 2014. 310--320. Google Scholar

[22] Naveed M. The Fallacy of Composition of Oblivious RAM and Searchable Encryption. IACR Cryptology ePrint Archive, 2015, 2015, 668. Google Scholar

[23] Cash D, Jarecki S, Jutla C, et al. Highly-scalable searchable symmetric encryption with support for boolean queries. In: Proceedings of Annual Cryptology Conference. Berlin: Springer, 2013. 353--373. Google Scholar

[24] Demertzis I, Papadopoulos S, Papapetrou O, et al. Practical private range search revisited. In: Proceedings of the 2016 International Conference on Management of Data, 2016. 185--198. Google Scholar

[25] Kamara S, Moataz T. Boolean searchable symmetric encryption with worst-case sub-linear complexity. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham: Springer, 2017. 94--124. Google Scholar

[26] Meng X, Kamara S, Nissim K, et al. Grecs: graph encryption for approximate shortest distance queries. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, 2015. 504--517. Google Scholar

[27] Kamara S, Moataz T. SQL on structurally-encrypted databases. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. Cham: Springer, 2018. 149--180. Google Scholar

[28] Blass E O, Mayberry T, Noubir G, et al. Toward robust hidden volumes using write-only oblivious RAM. In: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, 2014. 203--214. Google Scholar

[29] Aviv A J, Choi S G, Mayberry T, et al. Oblivisync: practical oblivious file backup and synchronization. 2016,. arXiv Google Scholar

[30] Haider S, van Dijk M. Flat ORAM: A Simplified Write-Only Oblivious RAM Construction for Secure Processors. Cryptography, 2019, 3: 10 CrossRef Google Scholar

[31] Roche D S, Aviv A, Choi S G, et al. Deterministic, stash-free write-only oram. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017. 507--521. Google Scholar

[32] Li L, Datta A. Write-only oblivious RAM-based privacy-preserved access of outsourced data. Int J Inf Secur, 2017, 16: 23-42 CrossRef Google Scholar

[33] Zheng W, Dave A, Beekman J G, et al. Opaque: An oblivious and encrypted distributed analytics platform. In: Proceedings of the 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17), 2017. 283--298. Google Scholar

[34] Shaon F, Kantarcioglu M, Lin Z, et al. Sgx-bigmatrix: a practical encrypted data analytic framework with trusted processors. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017. 1211--1228. Google Scholar

[35] Hoang T, Ozmen M O, Jang Y. Hardware-Supported ORAM in Effect: Practical Oblivious Search and Update on Very Large Dataset. Proc Privacy Enhancing Technologies, 2019, 2019(1): 172-191 CrossRef Google Scholar

[36] Ahmad A, Kim K, Sarfaraz M I, et al. OBLIVIATE: a data oblivious filesystem for intel SGX. In: Proceedings of Network and Distributed System Security Symposium, 2018. Google Scholar

[37] Mandal A, Mitchell J C, Montgomery H, et al. Data oblivious genome variants search on Intel SGX. In: Data Privacy Management, Cryptocurrencies and Blockchain Technology. Cham: Springer, 2018. 296--310. Google Scholar

[38] Goldreich O. Foundations of Cryptography: Volume 2, Basic Applications. Cambridge: Cambridge University Press, 2009. Google Scholar

[39] Zhang Y, Katz J, Papamanthou C. All your queries are belong to us: the power of file-injection attacks on searchable encryption. In: Proceedings of the 25th USENIX Security Symposium (USENIX Security 16), 2016. 707--720. Google Scholar

[40] Katz J, Lindell Y. Introduction to Modern Cryptography. Boca Raton: CRC Press, 2014. Google Scholar

[41] Costan V, Devadas S. Intel SGX Explained. IACR Cryptology ePrint Archive, 2016. 2016(086): 1--118. Google Scholar

[42] Enron Email Dataset. Accessed December 15, 2019, 2019,https://www.cs.cmu.edu/~./enron. Google Scholar

[43] NLTK Project. Natural Language Toolkit. Accessed December 15, 2019, 2016, http://www.nltk.org. Google Scholar

  • Figure 1

    (Color online) Sample of the binary-search attack.

  • Figure 2

    (Color online) Sample process of one-time oblivious writing.

  • Figure 3

    (Color online) Sample process of ObliviousRead algorithm.

  •   

    Algorithm 1 ObliviousRead (textsfArray vec

    _Enclave:

    $~{\rm~result}~\leftarrow$ null;

    for $i$ from $1$ to $|~{\rm~vec}|$

    for $i$ from $1$ to $|\textsf{Array}[i]|$

    each bit of $\textsf{Array}[i]~\leftarrow~$ each bit of $\textsf{Array}[i]$ ${\rm~vec}[i]$; //Each item in textsfArray AND with vec one-one correspondence.

    end for

    ${\rm~result}~\leftarrow~~{\rm~result}~\mid~~\textsf{Array}[i]$; //The result OR with each other.

    end for

    Return result

  • Table 1  

    Table 1Comparison with prior forward private SSE schemes$^{\rm~a)}$

    Scheme ComputationCommunicationClient storageTP
    SearchUpdateSearchUpdate
    Fides [8] $O(a_w)$ $O(1)$ $O(a_w)$ $O(1)$ $O(K~\log~D)$ $-$
    Janus [8]$O({n_w}\cdot~{d_w})$ $O(1)$ $O(n_w)$ $O(1)$ $O(K~\log~D)$ $-$
    Orion [7] $O(n_w\log^2~N)$ $O(\log^2~N)$ $O(a_w)$ $O(\log^2~N)$ $O(1)$ $-$
    Mitra [7] $O(a_w)$ $O(1)$ $O(a_w)$ $O(1)$ $O(K~\log~D)$ $-$
    TWORAM [2]$\widetilde{O}(a_w~\log~N+\log^3N)$ $O(1)$ $O(a_w\cdot~\log~N\log\log~N)$ $O(1)$ $O(\log~^2~N)$ $\surd$
    SPS14 [13] $O({\rm~min}\{\mathop{}_{a_w+\log^2~N}^{n_w\log^3~N}\})$$n_w+\log~N$$O(K~\log~D)$ $\surd$
    Cetus $O(a_w)$ $O(N/M)$ $O(a_w)$ $O(1)$ $O(K\log~D)$ $\surd$

    a) $K$ is the number of keywords, $D$ is the number of documents in EDB, and $N$ is the number of (keyword, document) pairs. $n_w$ is the size of the search result set matching keyword $w$, $a_w$ is the total number of entries matching keyword $w$, $d_w$ is the number of deleted entries matching $w$. RT denotes round trip, BP denotes backward-private and TP denotes toward privacy.

  • Table 2  

    Table 2Comparison with EDB creation

    Implementation Time (s) Pairs (s) Storage (MB)
    ClientServer
    Our scheme (with SHA-256) 1961 3162617.991892
    Our scheme (with SHA-512) 2745 2259318.003783
    Fides 39653 156416803
  •   

    Algorithm 2 Setup$\lambda$)

    ${k\xleftarrow{\$}~{\{0,~1\}^\lambda}}$, cyc$~\leftarrow~0$;

    ${r_h',r_m'\xleftarrow{\$}~{\{0,~1\}^\lambda}}$; //Input of random mask for lightweight re-encryption in SGX.

    textsfMain$[N]$, textsfHold$[M]~\leftarrow$ empty map; //Initialize main area and holding area.

    $\sigma~\leftarrow~$ textsfCur$[W]$, textsfsM$[N]$, textsfsH$[M]$;

    textsfEDB $~\leftarrow~\textsf{Main},~\textsf{Hold}$; //$N$ blocks in textsfMain and $M$ blocks in textsfHold together form encryption database.

    $L~\leftarrow~N/M$;

    Send textsfEDB to the server.

  •   

    Algorithm 3 Update$k,{\rm~op},~\sigma,{\rm~id},w$; textsfEDB

    //update index.

    Client:

    fnl $\xleftarrow{\$}~\{x|~x~<~N,~x~\in~\mathbb{N},~\textsf{sM}[x].{\rm~sta}~=~0$; //Choose an empty slot in main area uniform randomly.

    if $\textsf{Cur}[w]$ = null then

    $\textsf{Cur}[w].{\rm~key}||~\textsf{Cur}[w].{\rm~pos}~\leftarrow~{\rm~null}$; //$w$ is first add.

    end if

    pre $\leftarrow~\textsf{Cur}[w].{\rm~key}||~\textsf{Cur}[w].{\rm~pos}$; //Record the previous item of $w$.

    $\textsf{Cur}[w].{\rm~key}\xleftarrow{\$}~\{0,1\}^\lambda$;

    $\textsf{Cur}[w].{\rm~pos}\leftarrow~{\rm~fnl}$; //Initialize encrypt key and position of newly add item.

    val$\leftarrow~(E_k({\rm~id})||E_{\textsf{Cur}[w].{\rm~key}}({pre}))\oplus~H(r_h&apos;)$;

    $\textsf{sH}[{\rm~cyc}~].{\rm~sta}~\leftarrow~$ 1; //cyc-th slot in holding area is full.

    $\textsf{sH}[{\rm~cyc].des}~\leftarrow~$ fnl;

    Send val to the server;

    Server:

    $\textsf{Hold}[{\rm~cyc}]~\leftarrow~$ val; //Store val to cyc-th slot in holding area;

    OneTimeWritetextsfMain,Hold.

  •   

    Algorithm 4 OneTimeWritetextsfMain,Hold

    Client:

    vec$[M]\leftarrow~\emptyset$;

    for $i~=~0$ to $M-1$

    if cyc$\cdot~L~\leqslant~{\textsf{sH}}[i].{\rm~des}~<$ (cyc+$1)\cdot~L-1$ then

    vec$[i]$ = textsfsH$[i].{\rm~des}$; //Record all the final position of blocks in textsfHold which is in $L$ position of textsfMain

    else

    vec$[i]~=~0$;

    end if

    end for

    Send vec $r_m,r_m&apos;,r_h,r_h&apos;$ to Enclave;

    Server:

    Send textsfMaincyc$\cdot~L\sim~({\rm~cyc}+1)\cdot~L-1$ and textsfHold to Enclave;

    Enclave:

    I$(L,M)~\leftarrow~\{0\}$; //Initialize a $L\times~M$ permutation matrix I.

    CleanVec$[L]\leftarrow~\{1\}$; //Initialize a vector of length $L$ where each term is $1$.

    for $i~=~0$ to $M-1$

    fnl = vec$[i]-L\cdot~{\rm~cyc}$

    I$({\rm~fnl},i)~=~1$; //Constructing I according to vec

    CleanVecfnl $\leftarrow~0$; //Clean the blocks in textsfMain which will be replaced by the blocks in textsfHold

    end for

    array$_h$ $\leftarrow$ textsfHold;

    for $i~=~0$ to $M-1$

    if $i\leq$ cyc then

    array$_h$$[i]~\leftarrow$ array$_h$$[i]~\oplus~H(r_h&apos;)$;

    else

    array$_h$$[i]~\leftarrow$ array$_h$$[i]~\oplus~H(r_h)$; //cyc is public so that the IF sentence leaks no information.

    end if

    end for

    array$_m$ $\leftarrow$ textsfMaincyc$\cdot~L\sim~({\rm~cyc}+1)\cdot~L-1$

    for $i=0$ to $L-1$

    array$_m$$[i]~\leftarrow$ array$_m$$[i]~\oplus~H_{r_m}({\rm~cyc}\cdot~L+i)$;//Remove the previous mask.

    end for

    res$[L],{\rm~res}&apos;[L]\leftarrow~\{0\}$;

    for $i=0$ to $L-1$

    res$[i]$ = ObliviousRead(array$_h$ I$(i,*)$); //If there has a block of textsfHold which should be placed in $i$ slot, the result is this block, otherwise $0$.

    res$&apos;[i]$ = res$[i]~\mid$ (array$_m[i]~\&$CleanVec$[i]$)$\}\oplus~H_{r_m&apos;}({\rm~cyc}\cdot~L+i)$; //$\mid$ is OR and $\&$ is AND and the result is either the original block in the main area or the block transferred from the holding area.

    end for

    Send res$&apos;[i]$ to the server.

    Server:

    textsfMaincyc$\cdot~L\sim~({\rm~cyc}+1)\cdot~L-1$ $\leftarrow$ res$&apos;$;

    ${\rm~cyc}:=({\rm~cyc}+1)\mod~M$; //Increment counter

    if cyc = 0 then

    $~{\rm~Ser}~\leftarrow~r_m&apos;$;

    $r_m\leftarrow~r_m&apos;,~r_h~\leftarrow~~r_h&apos;$;

    $r_m&apos;,~r_h&apos;~\xleftarrow{\$}~{\{0,~1\}^\lambda}$;

    end if

  •   

    Algorithm 5 Search$K,~w,~~\sigma$; textsfEDB

    //Search in index and file storage.

    Client:

    while cyc $\neq~0$ do

    OneTimeWritetextsfMaintextsfHold; //Before each search, you must ensure that the main area has been updated once, that is, the blocks in the holding area have been transferred to the main area for a round.

    end while

    key, pos $\leftarrow$textsfCur$[w]$; //Record the encrypt key and position of the last item with $w$.

    Token $\leftarrow$ key, pos;

    Send Token Ser to the server;

    Server:

    textsfResVal $\leftarrow~\emptyset$;

    while pre is full do

    val $\leftarrow$ textsfMainpos;

    $E_k({\rm~id}),E_{{\rm~key}}({\rm~pre})~\leftarrow~{\rm~val}~\oplus~H_{{\rm~Ser}}({\rm~pos})$; //Remove the mask and retrieve the file identifier and the pointer of previous item.

    textsfResVal = textsfResVal $\cup~E_k({\rm~id})$;

    ${\rm~pre}~=~D_{\rm~key}(E_{\textsf{Cur}[w].{\rm~key}}({\rm~pre}))$; //Decrypt the pointer information of previous item.

    key, pos $\leftarrow$ pre;

    end while

    Send textsfResVal to the client;

    Client:

    textsfIdSet $\leftarrow~\emptyset$; //Indentifier results set.

    textsfIdSet $\leftarrow~\textsf{IdSet}~\cup~D_k(E_k({\rm~id}))$;

    Send textsfIdSet to the server;

    Server:

    textsfFileSet $\leftarrow~\emptyset$; //File results set.

    textsfFileSet $\leftarrow~\textsf{FileSet}\cup~\textsf{Main}.{\rm~get}({\rm~id})$.

  •   

    Algorithm 6 Simulation of update$|w|$)

    cyc := (cyc + $1)~\mod~M$; cyc is $0$ Ser$\leftarrow~r$; $r,r&apos;\xleftarrow{\$}~\{0,1\}^\lambda$;

    id mask mask$&apos;$$r,r&apos;\xleftarrow{\$}~\{0,1\}^\lambda$;

    pkey, ppos $\leftarrow~\bot$;

    $H_{\rm~table}~\leftarrow~H_{\rm~table}~\cup~(r,{\rm~mask}),~H_{\rm~table}~\leftarrow~H_{\rm~table}~\cup~(r&apos;,{\rm~mask&apos;})$;

    for $i~=~0$ to $|w|$

    id ckey, key$\xleftarrow{\$}~\{0,1\}^\lambda$;

    textsfcPosrm cyc$\xleftarrow{\$}~\{x|~x~<~N,~x~\in~\mathbb{N}$;

    val$\leftarrow~({\rm~id}||E_{\rm~ckey}({\rm~pkey}||{\rm~ppos}))\oplus~{\rm~mask}$;

    $\textsf{Hold}[{\rm~cyc}]~\leftarrow~$ val;

    mask$&apos;$ $\xleftarrow{\$}~\{0,1\}^\lambda$;

    for $i=0$ to $L~-1$

    if textsfcPos$[j]~=~i$ then

    textsfMaincyc$\cdot~L~+i~$ = textsfHold$j$ $\oplus~{\rm~mask}~\oplus~{\rm~mask&apos;}$

    else

    textsfMaincyc$\cdot~L~+i$ = textsfMaincyc$\cdot~L~+i$ $\oplus~{\rm~mask}~\oplus~{\rm~mask&apos;}$;

    end if

    end for

    pkey $\leftarrow$ ckey;

    ppos $\leftarrow~\textsf{cPos}[{\rm~cyc}]$;

    end for

  •   

    Algorithm 7 Simulation of search${\rm~Result}(w)$)

    $\bar{w}\leftarrow~{\rm~min}({\rm~Result}(w))$;

    while ${\rm~cyc}~\neq~0$ do

    for $i=0$ to $L~-1$

    if textsfcPos$[j]~=~i$ then

    textsfMaincyc$\cdot~L~+i$ = textsfHold$j$ $\oplus~{\rm~mask}~\oplus~~{\rm~mask&apos;}$;

    else

    textsfMaincyc$\cdot~L~+i$ = textsfMaincyc$\cdot~L~+i$ $\oplus~{\rm~mask}~\oplus~{\rm~mask&apos;}$;

    end if

    end for

    cyc := ( cyc + $1)~\mod~M$;

    end while

    Ser$\leftarrow~r&apos;$;

    if (Ser out$\in~H_{\rm~table}$ then

    mask$&apos;$ $\leftarrow~~{\rm~out}$;

    end if

    if $~{\rm~Cur}[\bar{w}]~=~\bot$ then

    return $\emptyset$;

    else

    Token$\leftarrow~({\rm~Cur}[\bar{w}].{\rm~key},~{\rm~Cur}[\bar{w}].{\rm~pos})$;

    end if

    key, pos $\leftarrow~{\rm~Token}$;

    while pre is full do

    val $\leftarrow$ textsfMainpos;

    id, $E_{\rm~key}({\rm~pre})~\leftarrow~~{\rm~val}~\oplus~{\rm~mask&apos;}$;

    textsfResVal = textsfResVal $\cup~E_k({\rm~id})$;

    ${\rm~pre}~=~D_{\rm~key}(E_{\rm~key}({\rm~pre}))$;

    ${\rm~key,pos}~\leftarrow~{\rm~pre}$;

    end while

    textsfIdSet $\leftarrow~\emptyset$;

    textsfIdSet $\leftarrow~\textsf{IdSet}~\cup~D_k(E_k({\rm~id}))$;

    textsfFileSet $\leftarrow~\emptyset$;

    textsfFileSet $\leftarrow~\textsf{FileSet}\cup~\textsf{Main}.{\rm~get(id)}$;

    return Token textsfFileSet

qqqq

Contact and support