More Like this

1. Computationally Efficient Codes for Adversarial Binary-Erasure Channels

   https://doi.org/10.1109/ISIT54713.2023.10206731  

   Li, Sijie; Krishnan, Prasad; Jaggi, Sidharth; Langberg, Michael; Sarwate, Anand D. (June 2023, IEEE)

   We study communication models for channels with erasures in which the erasure pattern can be controlled by an adversary with partial knowledge of the transmitted codeword. In particular, we design block codes for channels with binary inputs with an adversary who can erase a fraction p of the transmitted bits. We consider causal adversaries, who must choose to erase an input bit using knowledge of that bit and previously transmitted bits, and myopic adversaries, who can choose an erasure pattern based on observing the transmitted codeword through a binary erasure channel with random erasures. For both settings we design efficient (polynomial time) encoding and decoding algorithms that use randomization at the encoder only. Our constructions achieve capacity for the causal and “sufficiently myopic” models. For the “insufficiently myopic” adversary, the capacity is unknown, but existing converses show the capacity is zero for a range of parameters. For all parameters outside of that range, our construction achieves positive rates. 

   more » « less
2. Cryptographic Binding Should Not Be Optional: A Formal-Methods Analysis of FIDO UAF Authentication

   Golaszewski, Enis; Sherman, Alan T.; Zieglar, Edward (July 2023, ACM CCS (submitted))

   s a case study in cryptographic binding, we present a formal-methods analysis of the Fast IDentity Online (FIDO) Universal Authentication Framework (UAF) authentication protocol's cryptographic channel binding mechanisms. First, we show that UAF's channel bindings fail to mitigate protocol interaction by a Dolev-Yao (DY) adversary, enabling the adversary to transfer the server's authentication challenge to alternate sessions of the protocol. As a result, in some contexts, the adversary can masquerade as a client and establish an authenticated session with a server, which might be a bank server. Second, we implement a proof-of-concept man-in-the-middle attack against eBay's open source FIDO UAF implementation. Third, we propose and verify an improvement of UAF channel binding that better resists protocol interaction, in which the client and the server, rather than the client alone, bind the server's challenge to the session. The weakness we analyze is similar to the vulnerability discovered in the Needham-Schroeder protocol over 25 years ago. That this vulnerability appears in FIDO UAF highlights the strong need for protocol designers to bind messages properly and to analyze their designs with formal-methods tools. UAF's channel bindings fail for four reasons: channel binding is optional; the client cannot authenticate the server's challenge, even when channel binding is used; the standard permits the server to accept incorrect channel bindings; and the protocol binds only to the communication endpoints and not to the protocol session. We carry out our analysis of the standard and our suggested improvement using the Cryptographic Protocol Shapes Analyzer (CPSA). To our knowledge, we are first to carry out a formal-methods analysis of channel binding in FIDO UAF, first to identify the structural weakness resulting from improper binding, and first to exhibit details of an attack resulting from this weakness. In FIDO UAF, the client can cryptographically bind protocol data (including a server-generated authentication challenge) to the underlying authenticated communication channel. To facilitate the protocol's adoption, the FIDO Alliance makes the channel binding optional and allows a server to accept incorrect channel bindings, such as when the client communicates through a network perimeter proxy. Practitioners should be aware that, when omitting channel binding or accepting incorrect channel bindings, FIDO UAF is vulnerable to a protocol-interaction attack in which the adversary tricks the client and authenticator to act as confused deputies to sign an authentication challenge for the adversary. In addition to enabling the server to verify the client's binding of the challenge to the channel, our improved mandatory dual channel-binding mechanism provides the following two advantages: (1) By binding the challenge to the channel, the server provides an opportunity for the client to verify this binding. By contrast, in the current standard, the client cannot authenticate the server's challenge. (2) It performs binding at the server where the authentication challenge is created, hindering an adversary from transplanting the challenge into another protocol execution. Our case study illustrates the importance of cryptographically binding context to protocol messages to prevent an adversary from misusing messages out of context. 

   more » « less
3. BodyWire-HCI: Enabling New Interaction Modalities by Communicating Strictly During Touch Using Electro-Quasistatic Human Body Communication

   https://doi.org/10.1145/3406238  

   Maity, Shovan; Yang, David; Redford, Scott Stanton; Das, Debayan; Chatterjee, Baibhab; Sen, Shreyas (December 2020, ACM Transactions on Computer-Human Interaction)

   null (Ed.)

   Communication during touch provides a seamless and natural way of interaction between humans and ambient intelligence. Current techniques that couple wireless transmission with touch detection suffer from the problem of selectivity and security, i.e., they cannot ensure communication only through direct touch and not through close proximity. We present  BodyWire-HCI , which utilizes the human body as a wire-like communication channel, to enable human–computer interaction, that for the first time, demonstrates selective and physically secure communication strictly during touch. The signal leakage out of the body is minimized by utilizing a novel, low frequency Electro-QuasiStatic Human Body Communication (EQS-HBC) technique that enables interaction strictly when there is a conductive communication path between the transmitter and receiver through the human body. Design techniques such as capacitive termination and voltage mode operation are used to minimize the human body channel loss to operate at low frequencies and enable EQS-HBC. The demonstrations highlight the impact of  BodyWire-HCI in enabling new human–machine interaction modalities for variety of application scenarios such as secure authentication (e.g., opening a door and pairing a smart device) and information exchange (e.g., payment, image, medical data, and personal profile transfer) through touch (https://www.youtube.com/watch?v=Uwrig2XQIH8). 

   more » « less
4. Linear Stochastic Bandits over a Bit-Constrained Channel

   Mitra, Aritra; Hassani, Hamed; Pappas, George (May 2023, Learning for Dynamics and Control Conference)

   One of the primary challenges in large-scale distributed learning stems from stringent communication constraints. While several recent works address this challenge for static optimization problems, sequential decision-making under uncertainty has remained much less explored in this regard. Motivated by this gap, we introduce a new linear stochastic bandit formulation over a bit-constrained channel. Specifically, in our setup, an agent interacting with an environment transmits encoded estimates of an unknown model parameter to a server over a communication channel of finite capacity. The goal of the server is to take actions based on these estimates to minimize cumulative regret. To this end, we develop a novel and general algorithmic framework that hinges on two main components: (i) an adaptive encoding mechanism that exploits statistical concentration bounds, and (ii) a decision-making principle based on confidence sets that account for encoding errors. As our main result, we prove that when the unknown model is d-dimensional, a channel capacity of O(d) bits suffices to achieve order-optimal regret. We also establish that for the simpler unstructured multi-armed bandit problem, 1 bit channel capacity is sufficient for achieving optimal regret bounds. Keywords: Linear Bandits, Distributed Learning, Communication Constraints 

   more » « less
5. Linear Stochastic Bandits over a Bit-Constrained Channel

   Mitra, Aritra; Hassani, Hamed; Pappas, George (June 2023, Learning for Dynamics and Control)

   One of the primary challenges in large-scale distributed learning stems from stringent communication constraints. While several recent works address this challenge for static optimization problems, sequential decision-making under uncertainty has remained much less explored in this regard. Motivated by this gap, we introduce a new linear stochastic bandit formulation over a bit-constrained channel. Specifically, in our setup, an agent interacting with an environment transmits encoded estimates of an unknown model parameter to a server over a communication channel of finite capacity. The goal of the server is to take actions based on these estimates to minimize cumulative regret. To this end, we develop a novel and general algorithmic framework that hinges on two main components: (i) an adaptive encoding mechanism that exploits statistical concentration bounds, and (ii) a decision-making principle based on confidence sets that account for encoding errors. As our main result, we prove that when the unknown model is d-dimensional, a channel capacity of O(d) bits suffices to achieve order-optimal regret. We also establish that for the simpler unstructured multi-armed bandit problem, 1 bit channel capacity is sufficient for achieving optimal regret bounds. 

   more » « less