Paper 2014/597

Invisible Adaptive Attacks

Jesper Buus Nielsen and Mario Strefler

Abstract

We introduce the concept of an \emph{invisible adaptive attack} (IAA) against cryptographic protocols. Or rather, it is a class of attacks, where the protocol itself is the attack, and where this cannot be seen by the security model. As an example, assume that we have some cryptographic security \emph{model} $M$ and assume that we have a current setting of the \emph{real world} with some cryptographic infrastructure in place, like a PKI. Select some object from this real world infrastructure, like the public key, $pk_0$, of some root certificate authority (CA). Now design a protocol $\pi$, which is secure in $M$. Then massage it into $\hat{\pi}$, which runs exactly like $\pi$, except that if the public key $pk$ of the root CA happens to be $pk_0$, then it will be completely insecure. Of course $\hat{\pi}$ should be considered insecure. However, in current security models existing infrastructure is modelled by generating it at random in the experiment defining security. Therefore, \emph{in the model}, the root CA will have a fresh, random public key $pk$. Hence $pk \ne pk_0$, except with negligible probability, and thus $M$ will typically deem $\hat{\pi}$ secure. The problem is that to notice the above attack in a security model, we need to properly model the correlation between $\hat{\pi}$ and $pk$. However, this correlation was made by the \emph{adversary} and it is naïve to believe that he will report this correlation correctly to the security model. It is the protocol itself and how to model it which is the attack. Furthermore, since a model cannot see a real world object, like "the current infrastructure", the correlation is invisible to the model when not reported by the adversary. Besides introducing the new concept of an invisible adaptive attack, we have the following contributions: \begin{enumerate} \item We show that a popular security model, the generalized universal composability (GUC) model introduced by Canetti, Dodis, Pass and Walfish in 2007\cite{CDPW07GUC}, allows an IAA, along the lines of the attack sketched above. This is not a problem specific to the GUC model, but it is more interesting to demonstrate this for the GUC model, as it was exactly developed to model security for protocols running with a common infrastructure which has been set up once and for all before the protocols are run. \item We show how to modify the GUC model to catch invisible adaptive attacks relative to existing infrastructure, introducing the \emph{strong externalized universal composability (SEUC)} model. Conceptually, when given a protocol to analyse, we will assume the \emph{worst case correlation} to the existing infrastructure, and we will deem it secure if it is secure in presence of this worst case correlation. I.e., a protocol is deemed insecure if there could \emph{exist} an IAA which is using the given protocol. We consider this new way to define security a main conceptual contribution of the paper. Properly modelling this conceptual idea is technical challenging and requires completely novel ideas. We consider this the main technical contribution of the paper. We prove that the new model has secure modular composition as the UC and the GUC model. \item We show that in the SEUC model any well-formed ideal functionality can be realised securely under standard computational assumptions and using an infrastructure, or setup assumption, known as an augmented common reference string. We do that by slightly modifying a protocol from \cite{CDPW07GUC} and reproving its security in the SEUC model. \end{enumerate} Our techniques seem specific to modelling IAAs relative to \emph{existing infrastructure}. One can, however, imagine more general IAAs, relative, for instance, to values being dynamically generated by secure protocols currently running in practice, like a broadcast service or a cloud service. We do not know how to model IAAs in general and hence open up a new venue of investigation.

Note: Added email to affiliation.