K-Cipher is a hardware-efficient bit-length parameterizable cipher, which has been designed to be a flexible component of computing and communication systems. K-Cipher is latency- and area-efficient and can operate on all block lengths from 24 up to 1024 bits. In the paper, we show that the recently published Mahzoun-Kraleva-Posteuca-Ashur attack on K-Cipher [M. Mahzoun, L. Kraleva, R. Posteuca and T. Ashur, Differential Cryptanalysis of K-Cipher, IEEE ISCC 2022] is characterized by complexity significantly higher than$2^{n}$, with$n$being the block length. This holds for all block lengths specified by the cipher. Whereas the developers of the attack suggest that the key of the 24-bit version of K-Cipher can be successfully recovered at complexity 229.7, we show that, in reality, the complexity of this attack is at least 246. Similarly, the complexity of attacking the 32-bit version of K-Cipher is at least 254and the complexity of attacking the 64-bit version of K-Cipher is at least 286. Our conclusion is that unless the attack is redesigned, K-Cipher cannot be considered broken at this time, and its security needs to be further investigated by the community.

Today’s data-intensive applications increasingly suffer from significant performance bottlenecks due to the limited memory bandwidth of the classical von Neumann architecture. Near-Data Processing (NDP) has been proposed to perform computation near memory or data storage to reduce data movement for improving performance and energy consumption. However, the untrusted NDP processing units (PUs) bring in new threats to workloads that are private and sensitive, such as private database queries and private machine learning inferences. Meanwhile, most existing secure hardware designs do not consider off-chip components trustworthy. Once data leaving the processor, they must be protected, e.g., via block cipher encryption. Unfortunately, current encryption schemes do not support computation over encrypted data stored in memory or storage, hindering the adoption of NDP techniques for sensitive workloads.In this paper, we propose SecNDP, a lightweight encryption and verification scheme for untrusted NDP devices to perform computation over ciphertext and verify the correctness of linear operations. Our encryption scheme leverages arithmetic secret sharing in secure Multi-Party Computation (MPC) to support operations over ciphertext, and uses counter-mode encryption to reduce the decryption latency. The security of the encryption and verification algorithm is formally proven. Compared with a non-NDP baseline, secure computation with SecNDP significantly reduces the memory bandwidth usage while providing security guarantees. We evaluate SecNDP for two workloads of distinct memory access patterns. In the setting of eight NDP units, we show a speedup up to 7.46× and energy savings of 18% over an unprotected non-NDP baseline, approaching the performance gain attained by native NDP without protection. Furthermore, SecNDP does not require any security assumption on NDP to hold, thus, using the same threat model as existing secure processors. SecNDP can be implemented without changing the NDP protocols and their inherent hardware design.

We present the design of a novel low latency, bit length parameterizable cipher, called the "K-Cipher". K-Cipher is particularly useful to applications that need to support ultra low latency encryption at arbitrary ciphertext lengths. We can think of a range of networking, gaming and computing applications that may require encrypting data at unusual block lengths for many different reasons, such as to make space for other unencrypted state values. Furthermore, in modern applications, encryption is typically required to complete inside stringent time frames in order not to affect performance. K-Cipher has been designed to meet these requirements. In the paper we present the K-Cipher design and discuss its rationale. We also present results from our ongoing security analysis which suggest that only 2 to 4 rounds are sufficient to make the cipher operate securely. Finally, we present synthesis results from 2-round 32-bit and 64-bit K-Cipher encrypt datapaths, produced using Intel’s ® 10 nm process technology. Our results show that the encrypt datapaths can complete in no more than 767 psec, or 3 clocks in 3.9-4.9 GHz frequencies, and are associated with a maximum area requirement of 1875 m2.

We study the security of the recently proposed implicit integrity methodology. Implicit integrity is a novel methodology that supports corruption detection without producing, storing or verifying mathematical summaries of the content such as MACs or ICVs, as typically done today. The main idea behind implicit integrity is that, whereas typical user data demonstrate patterns such as repeated bytes or words, decrypted data resulting from corrupted ciphertexts no longer demonstrate such patterns. Thus, by checking the entropy of decrypted ciphertexts, corruption can be possibly detected. Past contributions to the implicit integrity methodology have focused on observed patterns on client and server data that motivate the methodology, entropy definitions for arbitrarily small messages, and constructions that mitigate data corruption attacks. In this paper, we extend the known analytical results concerning implicit integrity addressing content replay attacks as well. We demonstrate that the class of cryptographic constructions known as `random oracles according to observer functions', which has been proposed for mitigating data corruption attacks, is actually simultaneously secure under two different adversary models: an input perturbing adversary performing content corruption attacks, and an oracle replacing adversary performing content replay attacks.

We present a cryptographic construction called IVP and study its security properties. IVP is a three level confusion-diffusion network that supports confidentiality and data integrity without requiring any message expansion of the content, such as, for example, for the computation of a MAC. We demonstrate that IVP is in the recently proposed class of cryptographic constructions called `Random Oracles according to Observer functions' (RO2). These constructions support a new notion of data integrity called `implicit' data integrity, which is based on the fact that user data usually demonstrate some patterns. If some ciphertext becomes corrupted, then the resulting plaintext no longer demonstrates such patterns. Thus, defense against data corruption attacks becomes possible by hardening the computation of ciphertext values, the plaintext of which demonstrates patterns. The encryption key is considered unknown.We show that IVP supports implicit data integrity and is secure in input perturbing and oracle replacing adversary models. The security of IVP is associated with a pattern which is frequently encountered among client and server data. This is the pattern of encountering 4 or more 16-bit words being equal to each other in a set of 32 words. The cryptographic strength of IVP is 30.215 bits, which is sufficient for defending against on-line data corruption and content replay attacks. Computationally, IVP is much lighter than other authenticated encryption approaches requiring only two additional rounds of AES, beyond the AES standard encryption rounds in the critical path. These correspond to some minimal computation overhead.

The rapidly growing body of research in adversarial machine learning has demonstrated that deep neural networks (DNNs) are highly vulnerable to adversarially generated images. This underscores the urgent need for practical defense techniques that can be readily deployed to combat attacks in real-time. Observing that many attack strategies aim to perturb image pixels in ways that are visually imperceptible, we place JPEG compression at the core of our proposed SHIELD defense framework, utilizing its capability to effectively "compress away" such pixel manipulation. To immunize a DNN model from artifacts introduced by compression, SHIELD "vaccinates" the model by retraining it with compressed images, where different compression levels are applied to generate multiple vaccinated models that are ultimately used together in an ensemble defense. On top of that, SHIELD adds an additional layer of protection by employing randomization at test time that compresses different regions of an image using random compression levels, making it harder for an adversary to estimate the transformation performed. This novel combination of vaccination, ensembling, and randomization makes SHIELD a fortified multi-pronged defense. We conducted extensive, large-scale experiments using the ImageNet dataset, and show that our approaches eliminate up to 98% of gray-box attacks delivered by strong adversarial techniques such as Carlini-Wagner's L2 attack and DeepFool. Our approaches are fast and work without requiring knowledge about the model.

We present the object class intrinsic filter conjecture. The aim of our work is to investigate design principles for machine learning algorithms that demonstrate false positive rates practically equal to zero. Reducing the false positive rate in machine learning algorithms is important in several fields. In cybersecurity for instance, algorithms that demonstrate few to almost zero false positive detections are typically more robust against attacks, where the adversary intentionally modifies the input in order to drive algorithms to some intended misclassification result. The object class intrinsic filter conjecture states that it is possible to augment standard machine learning algorithms with filters which depend on the object class which is being detected, and which, contrary to standard machine learning algorithms, use weight, bias and threshold values which are in part determined through training and in part functions of the runtime input (i.e., the input provided to algorithms at runtime for classification or scoring). This is a departure from some standard machine learning algorithms where weight and threshold values are determined only through training. We investigate the validity of our conjecture experimentally, presenting a hand gesture recognition system augmented with an object class intrinsic filter where the overall system's false positive rate is dropped to practically zero.

We address a well known problem of computer science, the problem of computing the probability that a given number of people m > 1 have the same birthday from among the members of a larger set of cardinality n ≥ m. The solution to this problem for m = 2 is well known and is usually referred to as the ‘birthday surprise probability’. A solution for m = 3 is also known and appears in the 2004 paper by DasGupta [The matching, birthday and the strong birthday problem: a contemporary review, Journal of Statistical Planning and Inference]. Further approximations to the solution of the related problem of computing the minimum number of people to interview until m people with the same birthday are found are presented in the seminal work by Klamkin and Newman [Extensions on the birthday surprise, Journal of Combinatorial Theory, 1967]. In this paper we present a new non-recursive approximation for the birthday probability applicable to any value of m > 1, which yields results that are experimentally proven accurate under the assumption that the number of birthdays is significantly larger than the number of people. Our expression is easy to compute, non-recursive, and applicable to values of m that can be arbitrarily larger than 2 or 3. We verify the validity of our result computing the birthday probability for different values of m, over billions of sets of random values generated using the Intel ® RDRAND hardware random number generation instruction. Our solution is based on a novel tree-based description of the event space which, if used, allows for the computation of the birthday probability efficiently and without involving recursions or multinomial distributions.

In this paper we present a feasibility study on the detection of a complex shape with good precision/recall, without using depth or color information and with minimal dependence on the machine learning training data set. Specifically, we present an algorithm that supports reliable open palm and fingertip contour line detection that satisfies the aforementioned requirements, using a training set of only 100 images. Conceptually, our work extends the framework by Coughlan et. al. [Efficient Deformable Template Detection and Localization without User Initiation, CVIU 2000], but provides new solutions to problems related to edge detection, finger template description and the design of a dynamic programming process used for determining optimal finger configurations. We discuss guidelines for building a practical working system demonstrating 82.82% precision as measured over 3,154 test frames associated with different backgrounds and environments. Our algorithm is associated with almost perfect recall in our experiments where finger sizes are between 16-80 pixels and the image resolution is VGA. By perfect recall we mean that the open palm is almost always detected.

We address the problem of detecting non-transient anomalies in visual information. By non-transient anomalies we mean changes in the way environments look that are persistent across time. Such changes may include leaving unattended bags at airport corridors, putting graffiti in building walls or damaging public property. Detecting non-transient anomalies is critical to security and surveillance in indoor and outdoor environments. We argue that existing off-the-shelf solutions to computer vision problems (e.g., image recognition, gesture recognition, text recognition) are not the most efficient when applied to detecting non-transient anomalies due to their associated computational overhead. In this paper we present a neural network-based architecture that addresses some of the limitations of the state of the art. To speed up computations, our architecture supports the processing of a large number of neurons in parallel. To reduce computational overheads, our architecture omits some of the Gaussian kernel-based feature extraction tasks performed by other systems. To classify visual anomalies as non-transient, our architecture uses a codebook-based algorithm which builds a history profile for every image segment. We describe our architecture and present some performance analysis.

This paper proposes a set of mechanisms for enhancing the security of the generalized MDC-2 mode of operation. The MDC-2 mode is used for constructing a double length hash function, using block cipher building blocks, and is believed to provide some collision resistance. Recently, several attacks on MDC-2 have been published - collision, first and second pre-image attacks, with complexity below the ideal. In this paper we analyze the root-cause of these attacks, as applied to the generalized MDC-2 mode, and propose techniques for mitigating them. By mitigating we mean that with our amendments the attacks are either not applicable, or their complexity is pushed to ideal.

In this paper we present system-wide analysis and performance tuning of a SPECweb SSL server. We focus on the banking workload of SPECweb because this workload is 100% SSL-enabled and thus designed to evaluate the SSL web server performance and capacity. In order to gain insight into the unique characteristics of a SPECweb banking server, we conduct extensive experiments and present module and function-level anatomy data. Based on our results, we propose methods for tuning up the server performance, alleviating some of the bottlenecks. One of our main results is that the SPECweb banking workload may not always be a realistic environment for measuring the capacity of an SSL server, due to the fact that it is burdened with overheads which are not related to cryptography and can be removed.

End-to-end communication encryption is considered necessary for protecting the privacy of user data in the Internet. Only a small fraction of all Internet traffic, however, is protected today. The primary reason for this neglect is economic, mainly security protocol speed and cost. In this paper we argue that recent advances in the implementation of cryptographic algorithms can make general purpose processors capable of encrypting packets at line rates. This implies that the Internet can be gradually transformed to an information delivery infrastructure where all traffic is encrypted and authenticated. We justify our claim by presenting technologies that accelerate end-to-end encryption and authentication by a factor of 6 and a high performance TLS 1.2 protocol implementation that takes advantage of these innovations. Our implementation is available in the public domain for experimentation.

We describe two novel techniques for multiplying polynomials which help with accelerating popular public key cryptographic algorithms like RSA and key exchange techniques like Elliptic Curve Diffie Hellman. The first technique is based on an algorithm for generating one-iteration Karatsuba-like formulae using graphs. The novelty of our approach lies on the correlation between graph properties (i.e. vertices, edges and sub-graphs) and the Karatsuba-like terms of big number multiplication routines. The second technique is an improvement over the one-iteration extension to Karatsuba proposed by Weimerskirch and Paar [2] that yields better performance when the input polynomials have odd number of coefficients. We present experimental data that show that our techniques boost the performance of public key and key exchange algorithms substantially.

A framework for designing a family of novel fast cyclic redundancy code (CRC) generation algorithms is presented. Our algorithms can ideally read arbitrarily large amounts of data at a time, while optimizing their memory requirement to meet the constraints of specific computer architectures. In addition, our algorithms can be implemented in software using commodity processors instead of specialized parallel circuits. We use this framework to design two efficient algorithms that run in the popular Intel IA32 processor architecture. First, a "slicing-by-4" algorithm doubles the performance of existing software-based table-driven CRC implementations based on the Sarwate [12] algorithm while using a 4-Kbyte cache footprint. Second, a "slicing-by-8" algorithm triples the performance of existing software-based CRC implementations while using an 8-Kbyte cache footprint. Whereas well-known software-based CRC implementations compute the current CRC value from a bitstream reading 8 bits at a time, our algorithms read 32 and 64 bits at a time, respectively (this is an extended version of a paper that appeared at the 10th IEEE International Symposium on Computers and Communications (ISCC '05) in Cartagena, Spain, in June 2005). The slicing-by-8 source code is freely available for experimentation and can be found at http://sourceforge.net/projects/slicing-by-8.

Packet scheduling is a critical component of router data paths because it allows routers to divide bandwidth intelligently between competing flows. A large number of scheduling algorithms annotate packets with time stamps and subsequently sort these packets according to their annotated time stamp values. For these algorithms the problems of efficiently tagging and sorting packets are still open to investigation. In this paper we propose a data structure and algorithm that reduces the latency of determining the packet with the smallest time stamp to a single memory access time and a small constant number of computation steps, independent of the number of flows serviced by the scheduler. The complexity of inserting a packet into our sorting data structure is logarithmic as a function of the ratio between the maximum packet size and minimum connection weight. The latency of inserting a packet can be hidden by performing insertions of several packets in parallel. This is the fastest sorting data structure known to us. One of the most efficient alternative implementation techniques proposed by Chao et. al. [20] is associated with logarithmic complexity of the scheduling decision time, as a function of the maximum value of packet time stamps. Our solution applies to many different packet fair queuing algorithms including Weighted Fair Queuing [28], Self-Clocked Fair Queuing (SCFQ) [28] and Start Time Fair Queuing [4].

A framework for designing a family of novel fast CRC generation algorithms is presented. Our algorithms can ideally read arbitrarily large amounts of data at a time, while optimizing their memory requirement to meet the constraints of specific computer architectures. In addition, our algorithms can be implemented in software using commodity processors instead of specialized parallel circuits. We use this framework to design two efficient algorithms that run in the popular Intel IA32 processor architecture. First, a 'slicing-by-4' algorithm doubles the performance of existing software-based, table-driven CRC implementations based on the Sarwate (August 1988) algorithm while using a 4K cache footprint. Second, a 'slicing-by-8' algorithm triples the performance of existing software-based CRC implementations while using an 8K cache footprint.

There is growing interest in network processor technologies capable of processing packets at line rates. Network processors are likely to be an integral part of next generation high-speed router and switch architectures, replacing the application-specific integrated circuits (ASICs) that are used in routers today. In this paper, we present the design, implementation and evaluation of NetBind, a high-performance, flexible and scalable binding tool for dynamically constructing data paths in network processor-based routers. The methodology that underpins NetBind balances the flexibility of network programmability against the need to process and forward packets at line speeds. To support the dynamic binding of components with the minimum addition of instructions in the critical path, NetBind modifies the machine language code of components at run time. To support fast data path composition, NetBind reduces the number of binding operations required for constructing data paths to a minimum set so that binding latencies are comparable with packet forwarding times. Data paths constructed using NetBind seamlessly share the resources of the same network processor. Resources are assigned during the binding process. We compare the performance of NetBind to the MicroACE system developed by Intel and show that NetBind provides better performance in comparison to MicroACE with smaller binding overhead. The NetBind source code described and evaluated in this paper is freely available on the Web (http://www.comet.columbia.edu/genesis/netbind) for experimentation. Copyright © 2005 John Wiley & Sons, Ltd.

Currently, the design, deployment, and refinement of new network architectures is a manual, ad hoc, and time-consuming process. We present the design, implementation, and evaluation of the Genesis Kernel, a programming system that automates the life cycle process for the creation, deployment, management, and architecting of network architectures. We discuss our experiences in building a spawning network that is capable of creating distinct virtual network architectures on-demand. The Genesis Kernel is based on a methodology that allows a child virtual network to operate on top of a subset of its parent's network resources and in isolation from other spawned virtual networks. We show through experimentation how a number of diverse network architectures can be spawned and architecturally refined. These spawned network architectures include a parent network that supports IP forwarding, and interior and exterior routing. We discuss how two child networks based on Cellular IP and Mobiware architectures can be spawned on the parent network to support wireless access to data and continuous media services, respectively.

Existing mobile systems (e.g., mobile IP, mobile ATM and third generation cellular systems) lack the intrinsic architectural flexibility to deal with the complexity of supporting adaptive mobile applications in wireless and mobile environments. We believe that there is a need to develop alternative network architectures from the existing ones to deal with the demands placed on underlying mobile signalling, adaptation management and wireless transport systems in support of new mobile services, e.g. interactive multimedia and web access. In this paper we present the design, implementation and evaluation of mobiware, a middleware technology that enables the introduction of new services in mobile networks. Mobiware provides a toolkit that service providers can utilize to build services that can dynamically exploit the intrinsic scalable properties of mobile multimedia applications in response to time-varying mobile network conditions. Based on an open programmable networking paradigm, mobiware runs on mobile devices, wireless access points and mobile-capable switch/routers providing a set of open programmable interfaces and distributed objects for adaptive mobile networking. Mobiware is software-intensive and is built on CORBA and Java distributed object technologies. The source code for mobiware v1.0 is freely available (comet.columbia.edu/mobiware) for experimentation.