The Number Crunch game : a simple vehicle for building algebraic reasoning skills

A newspaper numbers game based on simple arithmetic relationships is discussed. Its potential to give students of elementary algebra practice in semi-ad hoc reasoning and to build general arithmetic reasoning skills is explored.

An attack-localizing watermarking scheme for natural language documents

We present a text watermarking scheme that embeds a bitstream watermark Wi in a text document P preserving the meaning, context, and flow of the document. The document is viewed as a set of paragraphs, each paragraph being a set of sentences. The sequence of paragraphs and sentences used to embed watermark bits is permuted using a secret key. Then, English language sentence transformations are used to modify sentence lengths, thus embedding watermarking bits in the Least Significant Bits (LSB) of the sentences’ cardinalities. The embedding and extracting algorithms are public, while the secrecy and security of the watermark depends on a secret key K. The probability of False Positives is extremely small, hence avoiding incidental occurrences of our watermark in random text documents. Majority voting provides security against text addition, deletion, and swapping attacks, further reducing the probability of False Positives. The scheme is secure against the general attacks on text watermarks such as reproduction (photocopying, FAX), reformatting, synonym substitution, text addition, text deletion, text swapping, paragraph shuffling and collusion attacks.

Converse results to the Wiener attack on RSA

A well-known attack on RSA with low secret-exponent d was given by Wiener about 15 years ago. Wiener showed that using continued fractions, one can efficiently recover the secret-exponent d from the public key (N,e) as long as d < N 1/4. Interestingly, Wiener stated that his attack may sometimes also work when d is slightly larger than N 1/4. This raises the question of how much larger d can be: could the attack work with non-negligible probability for d=N 1/4 + ρ for some constant ρ > 0? We answer this question in the negative by proving a converse to Wiener’s result. Our result shows that, for any fixed ε > 0 and all sufficiently large modulus lengths, Wiener’s attack succeeds with negligible probability over a random choice of d < N δ (in an interval of size Ω(N δ )) as soon as δ > 1/4 + ε. Thus Wiener’s success bound dattack, which are guaranteed to succeed even when δ > 1/4. The known attacks in this class (by Verheul and Van Tilborg and Dujella) run in exponential time, so it is natural to ask whether there exists an attack in this class with subexponential run-time. Our second converse result answers this question also in the negative.

Crossword puzzle attack on NLS

NLS is one of the stream ciphers submitted to the eSTREAM project. We present a distinguishing attack on NLS by Crossword Puzzle (CP) attack method which is introduced in this paper. We build the distinguisher by using linear approximations of both the non-linear feedback shift register (NFSR) and the nonlinear filter function (NLF). Since the bias of the distinguisher depends on the Konst value, which is a key-dependent word, we present the graph showing how the bias of distinguisher vary with Konst. In result, we estimate the bias of the distinguisher to be around O(2^−30). Therefore, we claim that NLS is distinguishable from truly random cipher after observing O(2^60) keystream words. The experiments also show that our distinguishing attack is successful on 90.3% of Konst among 2^32 possible values. We extend the CP attack to NLSv2 which is a tweaked version of NLS. In result, we build a distinguisher which has the bias of around 2− 48. Even though this attack is below the eSTREAM criteria (2^−40), the security margin of NLSv2 seems to be too low.

Cryptanalysis of block ciphers with overdefined systems of equations

Several recently proposed ciphers, for example Rijndael and Serpent, are built with layers of small S-boxes interconnected by linear key-dependent layers. Their security relies on the fact, that the classical methods of cryptanalysis (e.g. linear or differential attacks) are based on probabilistic characteristics, which makes their security grow exponentially with the number of rounds N r r. In this paper we study the security of such ciphers under an additional hypothesis: the S-box can be described by an overdefined system of algebraic equations (true with probability 1). We show that this is true for both Serpent (due to a small size of S-boxes) and Rijndael (due to unexpected algebraic properties). We study general methods known for solving overdefined systems of equations, such as XL from Eurocrypt’00, and show their inefficiency. Then we introduce a new method called XSL that uses the sparsity of the equations and their specific structure. The XSL attack uses only relations true with probability 1, and thus the security does not have to grow exponentially in the number of rounds. XSL has a parameter P, and from our estimations is seems that P should be a constant or grow very slowly with the number of rounds. The XSL attack would then be polynomial (or subexponential) in N r> , with a huge constant that is double-exponential in the size of the S-box. The exact complexity of such attacks is not known due to the redundant equations. Though the presented version of the XSL attack always gives always more than the exhaustive search for Rijndael, it seems to (marginally) break 256-bit Serpent. We suggest a new criterion for design of S-boxes in block ciphers: they should not be describable by a system of polynomial equations that is too small or too overdefined.

Distinguishing attack on SOBER-128 with linear masking

We present a distinguishing attack against SOBER-128 with linear masking. We found a linear approximation which has a bias of 2^− − 8.8 for the non-linear filter. The attack applies the observation made by Ekdahl and Johansson that there is a sequence of clocks for which the linear combination of some states vanishes. This linear dependency allows that the linear masking method can be applied. We also show that the bias of the distinguisher can be improved (or estimated more precisely) by considering quadratic terms of the approximation. The probability bias of the quadratic approximation used in the distinguisher is estimated to be equal to O(2^− − 51.8), so that we claim that SOBER-128 is distinguishable from truly random cipher by observing O(2^103.6) keystream words.

Extending FORK-256 attack to the full hash function

In a paper published in FSE 2007, a way of obtaining near-collisions and in theory also collisions for the FORK-256 hash function was presented [8]. The paper contained examples of near-collisions for the compression function, but in practice the attack could not be extended to the full function due to large memory requirements and computation time. In this paper we improve the attack and show that it is possible to find near-collisions in practice for any given value of IV. In particular, this means that the full hash function with the prespecified IV is vulnerable in practice, not just in theory. We exhibit an example near-collision for the complete hash function.

How should future building structure and emergency response cope with bushfire attack?

Bushfires are regular occurrences in the Australian landscape which can, under adverse weather conditions, give rise to losses of life, property, infrastructure, environmental and cultural values. Where property loss is involved, historical surveys of house losses have focussed on ember, radiant heat and flame contact as key bushfire attack mechanisms. Although often noted, little work has been done to quantify the impact of fire generated or fire enhanced wind and pyro-convective events on house loss and to improve construction practice within Australia. It is well known that strong winds are always associated with bushfire events. It is less well known, although increasingly shown through anecdotal evidence, that bushfires are not a passive companion of wind, but indeed they interact with winds and can together cause significant damages to exposed buildings and ecological structures. Previous studies have revealed the effects of wind, fire and structure interactions with the result of increased pressure coefficient distributions on the windward side of a building downstream of a fire front. This paper presents a further analysis of the result in relations to the relevant standards and fire weather conditions. A review of wind code and bushfire code was conducted. Based on the result of the current study, the authors believe it is necessary to consider wind as an attack mechanism in bushfire events. The results of the study will also have implications on bushfire emergency management, design of emergency shelters, perception of danger, emergency evacuation and on risk assessment.

Multiple modular additions and crossword puzzle attack on NLSv2

NLS is a stream cipher which was submitted to the eSTREAM project. A linear distinguishing attack against NLS was presented by Cho and Pieprzyk, which was called Crossword Puzzle (CP) attack. NLSv2 is a tweak version of NLS which aims mainly at avoiding the CP attack. In this paper, a new distinguishing attack against NLSv2 is presented. The attack exploits high correlation amongst neighboring bits of the cipher. The paper first shows that the modular addition preserves pairwise correlations as demonstrated by existence of linear approximations with large biases. Next, it shows how to combine these results with the existence of high correlation between bits 29 and 30 of the S-box to obtain a distinguisher whose bias is around 2^−37. Consequently, we claim that NLSv2 is distinguishable from a random cipher after observing around 2^74 keystream words.

On algebraic immunity and annihilators

Algebraic immunity AI(f) defined for a boolean function f measures the resistance of the function against algebraic attacks. Currently known algorithms for computing the optimal annihilator of f and AI(f) are inefficient. This work consists of two parts. In the first part, we extend the concept of algebraic immunity. In particular, we argue that a function f may be replaced by another boolean function f^c called the algebraic complement of f. This motivates us to examine AI(f ^c ). We define the extended algebraic immunity of f as AI *(f)= min {AI(f), AI(f^c )}. We prove that 0≤AI(f)–AI *(f)≤1. Since AI(f)–AI *(f)= 1 holds for a large number of cases, the difference between AI(f) and AI *(f) cannot be ignored in algebraic attacks. In the second part, we link boolean functions to hypergraphs so that we can apply known results in hypergraph theory to boolean functions. This not only allows us to find annihilators in a fast and simple way but also provides a good estimation of the upper bound on AI *(f).

Detection of sinkhole attack in wireless sensor networks

Generally wireless sensor networks rely of many-to-one communication approach for data gathering. This approach is extremely susceptible to sinkhole attack, where an intruder attracts surrounding nodes with unfaithful routing information, and subsequently presents selective forwarding or change the data that carry through it. A sinkhole attack causes an important threat to sensor networks and it should be considered that the sensor nodes are mostly spread out in open areas and of weak computation and battery power. In order to detect the intruder in a sinkhole attack this paper suggests an algorithm which firstly finds a group of suspected nodes by analyzing the consistency of data. Then, the intruder is recognized efficiently in the group by checking the network flow information. The proposed algorithm's performance has been evaluated by using numerical analysis and simulations. Therefore, accuracy and efficiency of algorithm would be verified.

Effects of artificial shade on attack by the mahogany shoot borer, Hypsipyla robusta (Moore)

Swietenia macrophylla King (Meliaceae: Swietenioideae) provides one of the premier timbers of the world. The mahogany shoot borer Hypsipyla robusta Moore (Lepidoptera: Pyralidae) is an economically important pest of S. macrophylla throughout Asia, Africa and the Pacific. No viable method of controlling this pest is known. Previous observations have suggested that the presence of overhead shade may reduce attack by H. robusta, but this has not been investigated experimentally. This research was therefore designed to assess the influence of light availability on shoot-borer attack on S. macrophylla, by establishing seedlings under three different artificial shade regimes, then using these seedlings to test oviposition preference of adult moths, neonate larval survival and growth and development of shoot borer larvae. Oviposition preference of shoot borer moths was tested on leaves from seedlings grown under artificial shade for 63 weeks. A significant difference in choice was recorded between treatments, with 27.4 ± 1.5 eggs laid under high shade and 87.1 ± 1.8 under low shade. Neonate larval survival on early flushing leaflets of S. macrophylla did not differ significantly between shade treatments. Larval growth rate, estimated by measuring daily frass width, was significantly higher for those larvae fed on seedlings from the high and medium shade treatments (0.1 mm/day), than the low shade treatment (0.06 mm/day). In laboratory-reared larvae, the total mass of frass produced was significantly higher in the high shade treatment (0.4 g) than under the low shade treatment (0.2 g). Longer tunnel lengths were bored by larvae in plants grown under high shade (12.0 ± 2.4 cm) than under low shade (7.07 ± 1.9 cm). However, pupal mass under low shade was 48% higher than that under the high shade treatment, suggesting that plants grown under high shade were of lower nutritional quality for shoot borer larvae. These results indicate that shading of mahogany seedlings may reduce the incidence of shoot borer attack, by influencing both oviposition and larval development. The establishment of mahogany under suitable shade regimes may therefore provide a basis for controlling shoot borer attack using silvicultural approaches.

Practical attack on NLM-MAC scheme

The NLM stream cipher designed by Hoon Jae Lee, Sang Min Sung, Hyeong Rag Kim is a strengthened version of the LM summation generator that combines linear and non-linear feedback shift registers. In recent works, the NLM cipher has been used for message authentication in lightweight communication over wireless sensor networks and for RFID authentication protocols. The work analyses the security of the NLM stream cipher and the NLM-MAC scheme that is built on the top of the NLM cipher. We first show that the NLM cipher suffers from two major weaknesses that lead to key recovery and forgery attacks. We prove the internal state of the NLM cipher can be recovered with time complexity about nlog7×2, where the total length of internal state is 2⋅n+22⋅n+2 bits. The attack needs about n2n2 key-stream bits. We also show adversary is able to forge any MAC tag very efficiently by having only one pair (MAC tag, ciphertext). The proposed attacks are practical and break the scheme with a negligible error probability.

A low-cost attack on branch-based software watermarking schemes

In 2005, Ginger Myles and Hongxia Jin proposed a software watermarking scheme based on converting jump instructions or unconditional branch statements (UBSs) by calls to a fingerprint branch function (FBF) that computes the correct target address of the UBS as a function of the generated fingerprint and integrity check. If the program is tampered with, the fingerprint and integrity checks change and the target address will not be computed correctly. In this paper, we present an attack based on tracking stack pointer modifications to break the scheme and provide implementation details. The key element of the attack is to remove the fingerprint and integrity check generating code from the program after disassociating the target address from the fingerprint and integrity value. Using the debugging tools that give vast control to the attacker to track stack pointer operations, we perform both subtractive and watermark replacement attacks. The major steps in the attack are automated resulting in a fast and low-cost attack.