S&P'12 : A Framework to Eliminate Backdoors from Response-Computable Authentication

This paper "A Framework to Eliminate Backdoors from Response-Computable Authentication" is published in S&P'12.The authors are Shuaifu Dai, Tao Wei, Chao Zhang, Tielei Wang, Yu Ding, Zhenkai Liang, Wei Zou from Peking University, University of California, Georgia Institute of Technology School of Computing, and National University of Singapore.

Standard authentication mechanism can be divide into two type. In first type use challenge and response mechanism  and direct compare user response and respected response .This mechanism is widely employed in security system. For example, simple password checking, RC4. Second type feed user response to some authentication  mechanism to check if authentication success. This paper focus on eliminate these backdoor based on previous authentication type, response-computable authentication (RCA).
//how about move authentication type to type 2.

To gain the control of system and against authentication mechanism, it is common for hacker to plaint backdoor into system. For examples VSFTPD 2.3.4 Backdoor in 2011, Back Door in Commercial Shopping Cart. Typically, backdoor can be classify to three types. Adversary model of backdoor is described following. The attacker has chance to modify develop progress but cannot interfere deployment environment. For examples, attacker may modify  source code/binary directly, Thompson’s compiler backdoor[1], design to use weak cryptography algorithms. In this paper's 3 assumptions, 1) attacker cannot intercept code review and testing process.2) operating system is trusted. 3) password database is  trusted.

Backdoor of RCA can be classify to two type, type T1 and type T2. In type T1, bypass response comparison, backdoor bypass comparison between user response and respected response according to user input(U-trigger backdoor), global states(G-trigger backdoor) and internal states(I-trigger backdoor). Type T2 backdoor, controlling computation of expected response, can furthermore divide to two type, type T2a and type T2b. Type T2a backdoor's response computation depends on information other than challenge and password. Type 2b is response computation collision-based backdoor.

To address those backdoor, this paper propose a new RCA framework.

This framework eliminate backdoor by following steps.

1. Explicit response comparison, this step divide verification process into response computation and response comparison. And ensure that only task response comparison do is comparing user response and respect response. This step can eliminate T1 backdoor.
2. Function purification, this step ensure the only two factor involve in response computation is challenge and password. To make response computation a pure function(that is a function without side effects and deterministic), NaPu components employ a function level sandbox with global state isolation and iternel state reset. After this step T2a backdoors are eliminated.
3. Backdoor usability testing, this step use collision testing to find out high collision algorithms and eliminated T2b backdoors.

1. K. Thompson. Reflections on trusting trust. Communi- cations of the ACM, 27(8):761–763, 1984.