An improved preimage attack against HAVAL-3

Hash functions play an important role in constructing cryptographic schemes that provide security services, such as confidentiality in an encryption scheme, authenticity in an authentication protocol and integrity in a digital signature scheme and so on. Such hash function is needed to process a challenge, a message, an identifier or a private key. In this paper, we propose an attack against HAVAL-3 hash function, which is used in open source Tripwire and is included in GNU Crypto. Under the meet-in-the-middle (MITM) preimage attack framework proposed by Aoki and Sasaki in 2008, the one-wayness of several (reduced-)hash functions had been broken recently. However, most of the attacks are of complexity close to brute-force search. Focusing on reducing the time complexity of such MITM attacks, we improve the preimage attacks against HAVAL-3 hash function to within lower time complexity and memory requirement, compared with the best known attack proposed by Sasaki and Aoki in ASIACRYPT 2008. Besides the 256-bit variant of HAVAL-3, similar improvements can be applied to some truncated variants as well. Interestingly, due to the low complexity of our attack, the preimage attack applies to the 192-bit variant of HAVAL-3 for the first time.     

Implementation and evaluation of the Shim6 protocol in the Linux kernel

In the changing landscape of the todays Internet, several solutions are under investigation to allow efficient, flexible and scalable multihoming. One of the proposals is shim6, a host-based multihoming solution based on the use of multiple IPv6 addresses on each host. In this work, we first describe the main features of this protocol, then we explain our implementation of shim6, along with the associated security mechanisms in the Linux kernel and, finally, we evaluate its performance. In particular, we analyse the performance impact of the security mechanisms used by shim6 and the impact of shim6 on the performance of end-host systems, especially heavily loaded servers. We conclude by discussing the remaining open issues for a widespread deployment of host-based multihoming techniques such as shim6.     

Classification of packet contents for malware detection

Many existing schemes for malware detection are signature-based. Although they can effectively detect known malwares, they cannot detect variants of known malwares or new ones. Most network servers do not expect executable code in their in-bound network traffic, such as on-line shopping malls, Picasa, Youtube, Blogger, etc. Therefore, such network applications can be protected from malware infection by monitoring their ports to see if incoming packets contain any executable contents. This paper proposes a content-classification scheme that identifies executable content in incoming packets. The proposed scheme analyzes the packet payload in two steps. It first analyzes the packet payload to see if it contains multimedia-type data (such as avi, wmv, jpg){{\tt avi, wmv, jpg})} . If not, then it classifies the payload either as text-type (such as txt, jsp, asp){{\tt txt, jsp, asp})} or executable. Although in our experiments the proposed scheme shows a low rate of false negatives and positives (4.69% and 2.53%, respectively), the presence of inaccuracies still requires further inspection to efficiently detect the occurrence of malware. In this paper, we also propose simple statistical and combinatorial analysis to deal with false positives and negatives.     

Fast convergence to network fairness

Most AQM algorithms, such as RED, assure fairness through randomness in congestion notification. However, randomness results in fair allocation of network resources only when time limitations are not considered. This is not compatible with the current Internet, where traffic oscillations are frequent and the demand for fair treatment is rather urgent, due to short duration of most applications. Given the short duration of most modern Internet applications, fast convergence to fairness is necessitated. In this paper, we use fairness as the major criterion to adjust traffic and present a corresponding algorithm of active queue management, which is called Explicit Global Congestion Notifier (EGCN). EGCN notifies flows almost simultaneously about incipient congestion by marking packets arriving at the router’s queue, when the load in the network increases and buffer overflow is expected. This is a new approach compared with the random notification policy of RED or ECN. EGCN distributes the burden to adjust backward to more flows and consequently allows for smoother window adjustments. We elaborate on the properties of system-wide response in terms of fairness, smoothness and efficiency. Simulation results demonstrate a clear-cut advantage of the proposed scheme.     

ARMORY: An automatic security testing tool for buffer overflow defect detection

Program Buffer Overflow Defects (PBODs) are the stepping stones of Buffer Overflow Attacks (BOAs), which are one of the most dangerous security threats to the Internet. In this paper, we propose a kernel-based security testing tool, named ARMORY, for software engineers to detect PBODs automatically when they apply all kinds of testing, especially functional testing and unit testing, without increasing the testing workload. Besides, ARMORY does not need any attack instance, any training phase, or source code to finish its security testing. ARMORY can detect unknown PBODs. ARMORY not only can improve software quality, but also can reduce the amount of system resources used to protect a system. We implemented ARMORY in Linux kernel by modifying sys_read() system call and entry. S which deals all system call. Experimental results show that ARMORY can automatically detect PBODs when programmers test the functionality of their programs.     

Natural Language Compression on Edge-Guided text preprocessing

This paper presents Edge-Guided (E-G), an optimized text preprocessing technique for compression purposes. It transforms the original text into a word net, which stores all relationships between adjoining words. A specific directed graph is proposed to model this transformation: words are stored in vertices, whereas edges represent word transitions. Thus, the word net has a text representation which reflects the natural word order in the text, so it can be used directly for encoding purposes. A specific coding scheme is described at the top of the word net. It regards a text as a sequence of word transitions, in such a way that each word is encoded by traversing a specific edge from the vertex which stores the preceding word. This accomplishes a 1-order text preprocessing whose output is an intermediate byte representation that can be effectively encoded with universal techniques. This technique is called E-G₁ and performs on some variants.This experience is used to revisit the concept of word net. It is used to identify significative 2-word symbols by performing a specific transformation on frequent edges. The resultant transformed word net appends these 2-word symbols to the original word vocabulary, and allows a specific hierarchical relationship between them and their component words. The transformed approach also enhances the original coding scheme to handle these new features. A new technique, called E-G₂, approximates a 2-order model on words that also support specific variants.Both techniques are studied from empirical and experimental perspectives. Some compressors are also used to analyze the preprocessing ability of E-G with respect to different compression approaches. Competitive space/time trade-offs are achieved when our approaches are used to compress medium-large size texts. The best results are achieved when E-G preprocessing is coupled with high-order compressors such as Prediction by Partial Matching (PPM).     

A new tool for sharing and querying of clinical documents modeled using HL7 Version 3 standard

We present a new software tool called CDN (Collaborative Data Network) for sharing and querying of clinical documents modeled using HL7 v3 standard (e.g., Clinical Document Architecture (CDA), Continuity of Care Document (CCD)). Similar to the caBIG initiative, CDN aims to foster innovations in cancer treatment and diagnosis through large-scale, sharing of clinical data. We focus on cancer because it is the second leading cause of deaths in the US. CDN is based on the synergistic combination of peer-to-peer technology and the extensible markup language XML and XQuery. Using CDN, a user can pose both structured queries and keyword queries on the HL7 v3 documents hosted by data providers. CDN is unique in its design – it supports location oblivious queries in a large-scale, network wherein a user does not explicitly provide the location of the data for a query. A location service in CDN discovers data of interest in the network at query time. CDN uses standard cryptographic techniques to provide security to data providers and protect the privacy of patients. Using CDN, a user can pose clinical queries pertaining to cancer containing aggregations and joins across data hosted by multiple data providers. CDN is implemented with open-source software for web application development and XML query processing. We ran CDN in a distributed environment using Amazon EC2 as a testbed. We report its performance on real and synthetic datasets of discharge summaries. We show that CDN can achieve good performance in a setup with large number of data providers and documents.     

Optimizing the stretch of independent tasks on a cluster: From sequential tasks to moldable tasks

This paper addresses the problem of scheduling non-preemptive moldable tasks to minimize the stretch of the tasks in an online non-clairvoyant setting. To the best of the authors’ knowledge, this problem has never been studied before. To tackle this problem, first the sequential subproblem is studied through the lens of the approximation theory. An algorithm, called DASEDF, is proposed and, through simulations, it is shown to outperform the first-come, first-served scheme. Furthermore, it is observed that machine availability is the key to getting good stretch values. Then, the moldable task scheduling problem is considered, and, by leveraging the results from the sequential case, another algorithm, DBOS, is proposed to optimize the stretch while scheduling moldable tasks. This work is motivated by a task scheduling problem in the context of parallel short sequence mapping which has important applications in biology and genetics. The proposed DBOS algorithm is evaluated both on synthetic data sets that represent short sequence mapping requests and on data sets generated using log files of real production clusters. The results show that the DBOS algorithm significantly outperforms the two state-of-the-art task scheduling algorithms on stretch optimization.     

Informative labeling schemes for graphs

This paper introduces the notion of informative labeling schemes for arbitrary graphs. Let f(W) be a function on subsets of vertices W. An f labeling scheme labels the vertices of a weighted graph G in such a way that f(W) can be inferred (or at least approximated) efficiently for any vertex subset W of G by merely inspecting the labels of the vertices of W, without having to use any additional information sources.A number of results illustrating this notion are presented in the paper. We begin by developing f labeling schemes for three functions f over the class of n-vertex trees. The first function, SepLevel, gives the separation level of any two vertices in the tree, namely, the depth of their least common ancestor. The second, LCA, provides the least common ancestor of any two vertices. The third, Center, yields the center of any three given vertices v₁,v₂,v₃ in the tree, namely, the unique vertex z connected to them by three edge-disjoint paths. All of these three labeling schemes use O-bit labels, which is shown to be asymptotically optimal.Our main results concern the function Steiner(W), defined for weighted graphs. For any vertex subset W in the weighted graph G, Steiner(W) represents the weight of the Steiner tree spanning the vertices of W in G. Considering the class of n-vertex trees with M-bit edge weights, it is shown that for this class there exists a Steiner labeling scheme using O((M+logn)logn) bit labels, which is asymptotically optimal. It is then shown that for the class of arbitrary n-vertex graphs with M-bit edge weights, there exists an approximate-Steiner labeling scheme, providing an estimate (up to a factor of O(logn)) for the Steiner weight Steiner(W) of a given set of vertices W, using O bit labels.     

Notes on inverse bin-packing problems

In bin-packing problems, given items need to be packed using a minimum number of bins. Inverse bin-packing number problems, IBPN for short, assume a given set of items and number of bins. The objective is to achieve the minimum perturbation to the item-size vector so that all the items can be packed into the prescribed number of bins. In this paper, complexity status and approximation behavior for IBPN were investigated. Under the _Lp$L_p$-norm, ∀p∈{1,2,…,∞}$\forall p\in \{1,2,\dots ,\infty \}$, IBPN turns out to be NP-hard in the strong sense. IBPN under the _L1$L_1$-norm admits a polynomial time differential approximation scheme, and a fully polynomial time approximation scheme if a constant number of machines is provided as input. We also consider another IBPN variant where a specified feasible solution is given instead of a target bin number. The objective is to make the given solution optimal with minimum modification. We provide the hardness result for this problem.     

Abstract Interpretation for Proving Secrecy Properties in Security Protocols

A cryptographic protocol is a distributed program that can be executed by several actors. Since several runs of the protocol within the same execution are allowed, models of cryptoprotocols are often infinite. Sometimes, for verification purposes, only a finite and approximated model is needed. For this, we consider the problem of computing such an approximation and we propose to simulate the required partial execution in an abstract level. More precisely, we define an abstract finite category G ^a as an abstract game semantics for the SPC calculus, a dedicated calculus for security protocols. The abstract semantics is then used to build a decision procedure for secrecy correctness in security protocols.     

SARAH 4: A tool for (not only SUSY) model builders

We present the new version of the Mathematica package SARAH which provides the same features for a non-supersymmetric model as previous versions for supersymmetric models. This includes an easy and straightforward definition of the model, the calculation of all vertices, mass matrices, tadpole equations, and self-energies. Also the two-loop renormalization group equations for a general gauge theory are now included and have been validated with the independent Python code PyR@TE. Model files for FeynArts, CalcHep/CompHep, WHIZARD and in the UFO format can be written, and source code for SPheno for the calculation of the mass spectrum, a set of precision observables, and the decay widths and branching ratios of all states can be generated. Furthermore, the new version includes routines to output model files for Vevacious for both, supersymmetric and non-supersymmetric, models. Global symmetries are also supported with this version and by linking Susyno the handling of Lie groups has been improved and extended.     

On the concept of density control and its application to a hybrid optimization framework: Investigation into cutting problems

The Generate-and-Solve (GS) methodology is a hybrid approach that combines a metaheuristic component with an exact solver. GS has been recently introduced in the literature in order to solve cutting and packing problems, showing promising results. The GS framework includes a metaheuristic engine (e.g., a genetic algorithm) that works as a generator of reduced instances of the original optimization problem, which are, in turn, formulated as mathematical programming problems and solved by an integer programming solver. In this paper, we present an extended version of GS, focusing primarily on the concept of a new Density Control Operator (DCO). The role of this operator is to adaptively control the dimension of the reduced instances in such a way as to allow a much steadier progress towards a better solution, thereby avoiding premature convergence. In order to assess the potentials of this novel version of the GS methodology, we conducted computational experiments on a set of difficult benchmark instances of the constrained non-guillotine cutting problem. The results achieved are quantitatively and qualitatively discussed in terms of effectiveness and efficiency, showing that the proposed variant of the GS hybridization framework is highly suitable when effectiveness is a major requirement.     

一种高安全的门限群签密方案

为了满足群组通信的高安全性,将超椭圆曲线密码体制与Schno~数字签名体制相结合,设计了一个高安全的同时具有(t,n)门限签密和(k,l)门限共享验证功能的门限群签密方案.该方案克服了彭等人和Wang等人方案的安全缺陷,利用Desmedt等人的密钥重新分配协议的思想实现了门限签密和门限解签密的密钥先应式秘密共享.与现有的面向群组通信的广义门限签密方案相比,该方案能避免恶意信息的攻击,能抵抗内部欺诈和外部攻击,具有更小的通信代价和更高的安全性,特别适用于解决带宽受限网络的安全问题.     

An analysis of separable least squares data driven local coordinates for maximum likelihood estimation of linear systems

In this paper we study a novel parametrization for state-space systems, namely separable least squares data driven local coordinates (slsDDLC). The parametrization by slsDDLC has recently been successfully applied to maximum likelihood estimation of linear dynamic systems. In a simulation study, the use of slsDDLC has led to numerical advantages in comparison to the use of more conventional parametrizations, including data driven local coordinates (DDLC). However, an analysis of properties of slsDDLC, which are relevant to identification, has not been performed up to now. In this paper, we provide insights into the geometry and topology of the slsDDLC construction and show a number of results which are important for actual identification, in particular for maximum likelihood estimation. We also prove that the separable least squares methodology is indeed guaranteed to be applicable to maximum likelihood estimation of linear dynamic systems in typical situations.     

Cryptanalysis of an EPC Class-1 Generation-2 standard compliant authentication protocol

Recently, Chen and Deng (2009) proposed an interesting new mutual authentication protocol. Their scheme is based on a cyclic redundancy code (CRC) and a pseudo-random number generator in accordance with the EPC Class-1 Generation-2 specification. The authors claimed that the proposed protocol is secure against all classical attacks against RFID systems, and that it has better security and performance than its predecessors. However, in this paper we show that the protocol fails short of its security objectives, and in fact offers the same security level than the EPC standard it tried to correct. An attacker, following our suggested approach, will be able to impersonate readers and tags. Untraceability is also not guaranteed, since it is easy to link a tag to its future broadcast responses with a very high probability. Furthermore, readers are vulnerable to denial of service attacks (DoS), by obtaining an incorrect EPC identifier after a successful authentication of the tag. Moreover, from the implementation point of view, the length of the variables is not compatible with those proposed in the standard, thus further discouraging the wide deployment of the analyzed protocol. Finally, we propose a new EPC-friendly protocol, named Azumi, which may be considered a significant step toward the security of Gen-2 compliant tags.     

An analysis of the parametrization by data driven local coordinates for multivariable linear systems

In this paper, we study a novel parametrization for state-space systems, namely data driven local coordinates (DDLC) which have recently been introduced and applied. Even though DDLC has meanwhile become the default parametrization used in the system identification toolbox of the software package MATLAB, an analysis of properties of DDLC, which are relevant to identification, has not been performed up to now. In this paper, we provide insights into the geometry and topology of the DDLC construction and show a number of results which are important for actual identification such as maximum likelihood-type estimation.     

WPHACT 2.0: A fully massive Monte Carlo generator for four fermion physics at ee colliders

WPHACT 2.0 is the new fully massive version of a MC program and unweighted event generator which computes all Standard Model processes with four fermions in the final state at e⁺e⁻ colliders. The program can now generate unweighted events for any subset of all four fermion final states in a single run, by making use of dedicated pre-samples which can cover the entire phase space. Improvements with respect to WPHACT 1.0 include the Imaginary Fermion Loop gauge restoring scheme, new phase space mappings, a new input system, the possibility to compute subsets of Feynman diagrams and options for including ISR via QEDPS, running α_QED, CKM mixing, resonances in channels.     

An Even Closer Integration of Linear Arithmetic into Inductive Theorem Proving

To broaden the scope of decision procedures for linear arithmetic, they have to be integrated into theorem provers. Successful approaches e.g. in NQTHM or ACL2 suggest a close integration scheme which augments the decision procedures with lemmas about user-defined operators. We propose an even closer integration providing feedback about the state of the decision procedure in terms of entailed formulas for three reasons: First, to provide detailed proof objects for proof checking and archiving. Second, to analyze and improve the interaction between the decision procedure and the theorem prover. Third, to investigate whether the communication of the state of a failed proof attempt to the human user with the comprehensible standard GUI mechanisms of the theorem prover can enhance the speculation of auxiliary lemmas.     

Open-Source Model Checking

We present GMC², a software model checker for GCC, the open-source compiler from the Free Software Foundation (FSF). GMC², which is part of the GMC static-analysis and model-checking tool suite for GCC under development at SUNY Stony Brook, can be seen as an extension of Monte Carlo model checking to the setting of concurrent, procedural programming languages. Monte Carlo model checking is a newly developed technique that utilizes the theory of geometric random variables, statistical hypothesis testing, and random sampling of lassos in Büchi automata to realize a one- sided error, randomized algorithm for LTL model checking. To handle the function call/return mechanisms inherent in procedural languages such as C/C++, the version of Monte Carlo model checking implemented in GMC² is optimized for pushdown-automaton models. Our experimental results demonstrate that this approach yields an efficient and scalable software model checker for GCC.