On hash functions using checksums

We analyse the security of iterated hash functions that compute an input dependent checksum which is processed as part of the hash computation. We show that a large class of such schemes, including those using non-linear or even one-way checksum functions, is not secure against the second preimage attack of Kelsey and Schneier, the herding attack of Kelsey and Kohno and the multicollision attack of Joux. Our attacks also apply to a large class of cascaded hash functions. Our second preimage attacks on the cascaded hash functions improve the results of Joux presented at Crypto’04. We also apply our attacks to the MD2 and GOST hash functions. Our second preimage attacks on the MD2 and GOST hash functions improve the previous best known short-cut second preimage attacks on these hash functions by factors of at least 226 and 254, respectively. Our herding and multicollision attacks on the hash functions based on generic checksum functions (e.g., one-way) are a special case of the attacks on the cascaded iterated hash functions previously analysed by Dunkelman and Preneel and are not better than their attacks. On hash functions with easily invertible checksums, our multicollision and herding attacks (if the hash value is short as in MD2) are more efficient than those of Dunkelman and Preneel.

Cryptanalysis of the 10-Round Hash and Full Compression Function of SHAvite-3-512

In this paper, we analyze the SHAvite-3-512 hash function, as proposed and tweaked for round 2 of the SHA-3 competition. We present cryptanalytic results on 10 out of 14 rounds of the hash function SHAvite-3-512, and on the full 14 round compression function of SHAvite-3-512. We show a second preimage attack on the hash function reduced to 10 rounds with a complexity of 2497 compression function evaluations and 216 memory. For the full 14-round compression function, we give a chosen counter, chosen salt preimage attack with 2384 compression function evaluations and 2128 memory (or complexity 2448 without memory), and a collision attack with 2192 compression function evaluations and 2128 memory.

Cryptanalysis of Tav-128 Hash Function

Many RFID protocols use cryptographic hash functions for their security. The resource constrained nature of RFID systems forces the use of light weight cryptographic algorithms. Tav-128 is one such 128-bit light weight hash function proposed by Peris-Lopez et al. for a low-cost RFID tag authentication protocol. Apart from some statistical tests for randomness by the designers themselves, Tav-128 has not undergone any other thorough security analysis. Based on these tests, the designers claimed that Tav-128 does not posses any trivial weaknesses. In this article, we carry out the first third party security analysis of Tav-128 and show that this hash function is neither collision resistant nor second preimage resistant. Firstly, we show a practical collision attack on Tav-128 having a complexity of 237 calls to the compression function and produce message pairs of arbitrary length which produce the same hash value under this hash function. We then show a second preimage attack on Tav-128 which succeeds with a complexity of 262 calls to the compression function. Finally, we study the constituent functions of Tav-128 and show that the concatenation of nonlinear functions A and B produces a 64-bit permutation from 32-bit messages. This could be a useful light weight primitive for future RFID protocols.

Cryptographic Hash Functions

In the modern era of information and communication technology, cryptographic hash functions play an important role in ensuring the authenticity, integrity, and nonrepudiation goals of information security as well as efficient information processing. This entry provides an overview of the role of hash functions in information security, popular hash function designs, some important analytical results, and recent advances in this field.

Security Analysis of Randomize-Hash-then-Sign Digital Signatures

At CRYPTO 2006, Halevi and Krawczyk proposed two randomized hash function modes and analyzed the security of digital signature algorithms based on these constructions. They showed that the security of signature schemes based on the two randomized hash function modes relies on properties similar to the second preimage resistance rather than on the collision resistance property of the hash functions. One of the randomized hash function modes was named the RMX hash function mode and was recommended for practical purposes. The National Institute of Standards and Technology (NIST), USA standardized a variant of the RMX hash function mode and published this standard in the Special Publication (SP) 800-106. In this article, we first discuss a generic online birthday existential forgery attack of Dang and Perlner on the RMX-hash-then-sign schemes. We show that a variant of this attack can be applied to forge the other randomize-hash-then-sign schemes. We point out practical limitations of the generic forgery attack on the RMX-hash-then-sign schemes. We then show that these limitations can be overcome for the RMX-hash-then-sign schemes if it is easy to find fixed points for the underlying compression functions, such as for the Davies-Meyer construction used in the popular hash functions such as MD5 designed by Rivest and the SHA family of hash functions designed by the National Security Agency (NSA), USA and published by NIST in the Federal Information Processing Standards (FIPS). We show an online birthday forgery attack on this class of signatures by using a variant of Dean’s method of finding fixed point expandable messages for hash functions based on the Davies-Meyer construction. This forgery attack is also applicable to signature schemes based on the variant of RMX standardized by NIST in SP 800-106. We discuss some important applications of our attacks and discuss their applicability on signature schemes based on hash functions with ‘built-in’ randomization. Finally, we compare our attacks on randomize-hash-then-sign schemes with the generic forgery attacks on the standard hash-based message authentication code (HMAC).

Improved Security Analysis of Fugue-256 (Poster)

We present some improved analytical results as part of the ongoing work on the analysis of Fugue-256 hash function, a second round candidate in the NIST’s SHA3 competition. First we improve Aumasson and Phans’ integral distinguisher on the 5.5 rounds of the final transformation of Fugue-256 to 16.5 rounds. Next we improve the designers’ meet-in-the-middle preimage attack on Fugue-256 from 2480 time and memory to 2416. Finally, we comment on possible methods to obtain free-start distinguishers and free-start collisions for Fugue-256.

On the Collision and Preimage Resistance of Certain Two-Call Hash Functions

In this paper we present concrete collision and preimage attacks on a large class of compression function constructions making two calls to the underlying ideal primitives. The complexity of the collision attack is above the theoretical lower bound for constructions of this type, but below the birthday complexity; the complexity of the preimage attack, however, is equal to the theoretical lower bound. We also present undesirable properties of some of Stam’s compression functions proposed at CRYPTO ’08. We show that when one of the n-bit to n-bit components of the proposed 2n-bit to n-bit compression function is replaced by a fixed-key cipher in the Davies-Meyer mode, the complexity of finding a preimage would be 2 n/3. We also show that the complexity of finding a collision in a variant of the 3n-bits to 2n-bits scheme with its output truncated to 3n/2 bits is 2 n/2. The complexity of our preimage attack on this hash function is about 2 n . Finally, we present a collision attack on a variant of the proposed m + s-bit to s-bit scheme, truncated to s − 1 bits, with a complexity of O(1). However, none of our results compromise Stam’s security claims.

On Randomizing Hash Functions to Strengthen the Security of Digital Signatures

Halevi and Krawczyk proposed a message randomization algorithm called RMX as a front-end tool to the hash-then-sign digital signature schemes such as DSS and RSA in order to free their reliance on the collision resistance property of the hash functions. They have shown that to forge a RMX-hash-then-sign signature scheme, one has to solve a cryptanalytical task which is related to finding second preimages for the hash function. In this article, we will show how to use Dean’s method of finding expandable messages for finding a second preimage in the Merkle-Damgård hash function to existentially forge a signature scheme based on a t-bit RMX-hash function which uses the Davies-Meyer compression functions (e.g., MD4, MD5, SHA family) in 2 t/2 chosen messages plus 2 t/2 + 1 off-line operations of the compression function and similar amount of memory. This forgery attack also works on the signature schemes that use Davies-Meyer schemes and a variant of RMX published by NIST in its Draft Special Publication (SP) 800-106. We discuss some important applications of our attack.

Cryptanalysis of LASH

We show that the LASH-x hash function is vulnerable to attacks that trade time for memory, including collision attacks as fast as 2(4x/11) and preimage attacks as fast as 2(4x/7). Moreover, we briefly mention heuristic lattice based collision attacks that use small memory but require very long messages that are expected to find collisions much faster than 2 x/2. All of these attacks exploit the designers’ choice of an all zero IV. We then consider whether LASH can be patched simply by changing the IV. In this case, we show that LASH is vulnerable to a 2(7x/8) preimage attack. We also show that LASH is trivially not a PRF when any subset of input bytes is used as a secret key. None of our attacks depend upon the particular contents of the LASH matrix – we only assume that the distribution of elements is more or less uniform.

Algebraic attacks on SOBER-t32 and SOBER-t16 without stuttering

This paper presents algebraic attacks on SOBER-t32 and SOBER-t16 without stuttering. For unstuttered SOBER-t32, two different attacks are implemented. In the first attack, we obtain multivariate equations of degree 10. Then, an algebraic attack is developed using a collection of output bits whose relation to the initial state of the LFSR can be described by low-degree equations. The resulting system of equations contains 2^69 equations and monomials, which can be solved using the Gaussian elimination with the complexity of 2^196.5. For the second attack, we build a multivariate equation of degree 14. We focus on the property of the equation that the monomials which are combined with output bit are linear. By applying the Berlekamp-Massey algorithm, we can obtain a system of linear equations and the initial states of the LFSR can be recovered. The complexity of attack is around O(2^100) with 2^92 keystream observations. The second algebraic attack is applicable to SOBER-t16 without stuttering. The attack takes around O(2^85) CPU clocks with 2^78 keystream observations.

Building indifferentiable compression functions from the PGV compression functions

Preneel, Govaerts and Vandewalle (PGV) analysed the security of single-block-length block cipher based compression functions assuming that the underlying block cipher has no weaknesses. They showed that 12 out of 64 possible compression functions are collision and (second) preimage resistant. Black, Rogaway and Shrimpton formally proved this result in the ideal cipher model. However, in the indifferentiability security framework introduced by Maurer, Renner and Holenstein, all these 12 schemes are easily differentiable from a fixed input-length random oracle (FIL-RO) even when their underlying block cipher is ideal. We address the problem of building indifferentiable compression functions from the PGV compression functions. We consider a general form of 64 PGV compression functions and replace the linear feed-forward operation in this generic PGV compression function with an ideal block cipher independent of the one used in the generic PGV construction. This modified construction is called a generic modified PGV (MPGV). We analyse indifferentiability of the generic MPGV construction in the ideal cipher model and show that 12 out of 64 MPGV compression functions in this framework are indifferentiable from a FIL-RO. To our knowledge, this is the first result showing that two independent block ciphers are sufficient to design indifferentiable single-block-length compression functions.

EPC: a provably secure permutation based compression function

The security of permutation-based hash functions in the ideal permutation model has been studied when the input-length of compression function is larger than the input-length of the permutation function. In this paper, we consider permutation based compression functions that have input lengths shorter than that of the permutation. Under this assumption, we propose a permutation based compression function and prove its security with respect to collision and (second) preimage attacks in the ideal permutation model. The proposed compression function can be seen as a generalization of the compression function of MD6 hash function.

Rotational cryptanalysis of round-reduced Keccak

In this paper we attack round-reduced Keccak hash function with a technique called rotational cryptanalysis. We focus on Keccak variants proposed as SHA-3 candidates in the NIST’s contest for a new standard of cryptographic hash function. Our main result is a preimage attack on 4-round Keccak and a 5-round distinguisher on Keccak-f[1600] permutation — the main building block of Keccak hash function.

Cenários de impacto de uma eventual pandemia de gripe na população portuguesa : morbilidade, mortalidade e necessidade de cuidados de saúde

RESUMO - Introdução — O presente estudo descreve os cenários de impacto que uma eventual pandemia de gripe poderá ter na população portuguesa e nos serviços de saúde. Trata-se de uma versão actualizada dos cenários preliminares que têm vindo a ser elaborados e discutidos desde 2005. Material e métodos — Os cenários assumem que a pandemia ocorrerá em duas ondas das quais a primeira (taxa de ataque: 10%) será menos intensa do que a segunda (taxas de ataque: 20%, 25% ou 30%). Neste trabalho são descritos apenas os cenários respeitantes à situação mais grave (taxa de ataque global = 10% + 30%). A elaboração dos cenários utilizou o método proposto por Meltzer, M. I., Cox, N. J. e Fukuda, K. (1999) mas com quase todos os parâmetros adaptados à população portuguesa. Esta adaptação incidiu sobre: 1. duração da pandemia; 2. taxa de letalidade; 3. percentagem da população com risco elevado de complicações; 4. percentagem de doentes com suspeita de gripe que procurará consulta; 5. tempo entre o início dos sintomas e a procura de cuidados; 6. percentagem de doentes que terá acesso efectivo a antiviral; 7. taxa de hospitalização por gripe e tempo médio de hospitalização; 8. percentagem de doentes hospitalizados que necessitarão de cuidados intensivos (CI) e tempo de internamento em CI; 9. efectividade de oseltamivir para evitar complicações e morte. Resultados — Os cenários correspondentes à situação mais grave (taxa de ataque global: 10% + 30%) são apresentados sem qualquer intervenção e, também, com utilização de oseltamivir para fins terapêuticos. Os resultados sem intervenção para o cenário «provável» indicam: • número total de casos — 4 142 447; • número total de indivíduos a necessitar de consulta — 5 799 426; • número total de hospitalizações — 113 712; • número total de internamentos em cuidados intensivos — 17 057; • número total de óbitos — 32 051; • número total de óbitos, nas semanas com valor máximo — 1.a onda: 2551, 2.a onda: 7651. Quando os cenários foram simulados entrando em linha de conta com a utilização de oseltamivir (considerando uma efectividade de 10% e 30%), verificou-se uma redução dos valores dos óbitos e hospitalizações calculados. O presente artigo também apresenta a distribuição semanal, no período de desenvolvimento da pandemia, dos vários resultados obtidos. Discussão — Os resultados apresentados devem ser interpretados como «cenários» e não como «previsões». De facto, as incertezas existentes em relação à doença e ao seu agente não permitem prever com rigor suficiente os seus impactos sobre a população e sobre os serviços de saúde. Por isso, os cenários agora apresentados servem, sobretudo, para fins de planeamento. Assim, a preparação da resposta à eventual pandemia pode ser apoiada em valores cujas ordens de grandeza correspondem às situações de mais elevada gravidade. Desta forma, a sua utilização para outros fins é inadequada e é vivamente desencorajada pelos autores.

Persuasive system design methods to deliver a cardio-rehabilitation program of post mi outpatients

Las enfermedades no transmisibles provocan cada ano 38 millones de fallecimientos en el mundo. Entre ellas, tan solo cuatro enfermedades son responsables del 82% de estas muertes: las enfermedades cardiovasculares, las enfermedades crónicas respiratorias, la diabetes, y el cáncer. Se prevé que estas cifras aumenten en los próximos anos, ya que las tendencias indican que en el año 2030 las muertes por esta causa ascenderán a 53 millones de personas. La Organización Mundial de la Salud (OMS) considera importante buscar soluciones para afrontar esta situación y ha solicitado a los gobiernos del mundo la implementación de intervenciones para mejorar los hábitos de vida de las personas y reducir así el riesgo de desarrollo de enfermedades no trasmisibles. Cada año se producen 32 millones de infartos de miocardio y derrames celebrales, de los cuales 12.5 son mortales. En el mundo entre el 40% y 75% de la víctimas de un infarto de miocardio mueren antes de su ingreso en el hospital. En los casos que sobreviven, la adopción de un estilo de vida saludable puede evitar infartos sucesivo, y supone un ahorro potencial de 6 billones de euros al año. La rehabilitación cardiaca es un programa individualizado que aplica un método multidisciplinar para ayudar al paciente a recuperar su condición física, a gestionar la enfermedad cardiovascular y sus comorbilidades, a adoptar hábitos de vida saludables, y a promover su salud mental. La rehabilitación cardiaca requiere la total involucración y motivación del paciente, solo de esta manera se podrán promover hábitos saludables y mejorar la gestión y prevención de su enfermedad. Aunque la participación en los programas de rehabilitación cardiaca es baja, hoy en día existen programas de rehabilitación cardiaca que el paciente puede realizar en su casa. Estos suponen una solución prometedora para aumentar la participación. La rehabilitación cardiaca se considera una intervención integral donde los modelos de psicología de la salud son aplicados para promover un cambio en el estilo de vida de las personas así como para ayudarles a afrontar su propia enfermedad. Existen métodos para implementar cambios de hábitos y de aptitud, y también se considera muy relevante promover no solo el bienestar físico sino también el mental. Existen tecnologías que promueven los cambios de comportamientos en los seres humanos. En concreto, las tecnologías persuasivas y los sistemas de apoyo al cambio de comportamientos modelan las características, las estrategias y los métodos de diseño para promover cambios usando la tecnología. Pero estos modelos tienen algunas limitaciones: todavía no se ha definido que rol tienen las emociones en el cambio de comportamientos y como traducir los métodos de la psicología de la salud en la tecnología. Esta tesis se centra en tres elementos que tienen un rol clave en los cambios de hábitos y actitud: el estado físico, el estado mental, y la tecnología. -Estado de salud: un estado de salud critico puede modificar la actitud del ser humano respecto al cambio. A la vez un buen estado de salud hace que la necesidad del cambio sea menos percibida. -Estado emocional: la actitud tiene un componente afectivo. Los estados emocionales negativos pueden reducir la habilidad de una persona para adoptar nuevos comportamientos. La salud mental es la situación ideal donde los individuos tienen predisposición a los cambios. La tecnología puede ayudar a las personas a adoptar nuevos hábitos, así como a mantener una salud física y mental. Este trabajo de investigación se centra en el diseño de tecnologías para la mejora del estado físico y emocional de las personas. Se ha propuesto un marco de diseño llamado “Well.Be.Sign”. El marco se basa en tres aspectos: El marco teórico: representa los elementos que se tienen que definir para diseñar tecnologías para promover el bienestar de las personas. -El diagrama de influencia: presenta las fuerzas de ‘persuasión’ en el contexto de la salud. El rol de las tecnologías persuasivas ha sido contextualizado en una dimensión donde otros elementos influencian el usuario.  El proceso de diseño: describe el proceso de diseño utilizando una metodología iterativa e incremental que aplica una combinación de métodos de diseño existentes (Diseño Orientado a Objetivos, Diseño de Sistemas Persuasivos) así como elementos originales de este trabajo de investigación. Los métodos se han aplicados para diseñar un sistema que ofrezca un programa de tele-rehabilitación cardiaca. Inicialmente se ha diseñado un prototipo de acuerdo con las necesidades del usuario. En segundo lugar, el prototipo se ha extendido especificando la intervención requerida para al programa de rehabilitación cardiaca. Finalmente el sistema se ha desarrollado y validado en un ensayo clínico con grupo control, donde se observaron las variaciones del estado cardiovascular, el nivel de conocimiento acerca de la enfermedad, la percepción de la enfermedad, la persistencia de hábitos saludables, y la aceptabilidad del sistema. Los resultados muestran que el grupo de intervención tiene una superior capacidad cardiovascular, mejor conocimiento acerca de la enfermedad, y más percepción de control de la enfermedad. Asimismo, en algunos casos se ha registrado persistencia de los hábitos de ejercicios 6 meses después del uso del sistema. Otros dos estudios se han presentado para demonstrar la relevancia del estado emocional del usuario en el diseño de aplicaciones para la promoción del bienestar.  En personas con una grave enfermedad crónica como la insuficiencia cardiaca, donde se ha presentado las conexiones entre estado de salud y estado emocional. En el estudio se ensena la relaciones que tienen los síntomas y las emociones negativas y como un estado negativo emocional puede empeorar la condición física del paciente. -Personas con trastornos del humor: el estudio muestra como las emociones pueden tener un impacto en la percepción de la tecnología por parte del usuario. ABSTRACT Noncommunicable diseases (NCDs) cause the death of 38 million people every year. Four major NCDs are responsible for 82% of these deaths: cardio vascular disease, chronic respiratory disease, diabetes and cancer. These pandemic numbers are projected to raise to 53 million deaths in 2030, and for this reason the assembly of the World Health Organization (WHO) considers communicable diseases as an urgent need to be addressed. It is also a trend to advocate the adoption of mobile technology to deliver health services and to promote healthy behaviours among citizens, but adopting healthS promoting lifestyle is still a difficult task facing human tendencies. Within this context, there is a promising opportunity: persuasive technologies. These technologies are intentionally designed to change a person’s attitudes or behaviours; when applied in this context, than can be used to change health-related attitudes, beliefs, and behaviours. Each year there are 32 million heart attacks and strokes globally, of which about 12.5 million are fatal. Worldwide between 40 and 75% of all heart-attack victims die before reaching hospital. Avoiding a second heart attack by improving adherence to lifestyle and medication regimens has a cost saving potential of around €6 billion per year. In most of the cases the cardiovascular event has been provoked by unhealthy lifestyle. Furthermore, after an MI event the patient's decision to adopt or not healthier behaviour will influence the progress of the disease. Cardio-rehabilitation is an individualized program that follows a multidisciplinary approach to support the user to recover from the Myocardial Infarction, manage the Cardio Vascular Disease and the comorbidities, adopt healthy habits, and cope with any emotional distress. Cardio- rehabilitation requires patient participation and willingness to perform behavioral modifications and change the attitude toward the management and prevention of the disease. Participation in the Cardio Rehabilitation program is not high; the home-based rehabilitation program is a promising solution to increase participation. Nowadays cardio rehabilitation is considered a comprehensive intervention in which models of health psychology are applied to promote the behaviour change of the individuals. Relevant methods that have been successfully applied to foster healthy habits include the Health Belief Model and the Trans Theoretical Model. Studies also demonstrate the importance to promote not only the physical but also the mental well being of the individuals. The idea of also promoting behaviour change using technologies has been defined by the literature as persuasive technologies or behaviour change support systems, in which the features, the strategies and the design method have been modelled to foster the behaviour change using technology. Limitations have been found in this model: there is still research to be done on the role of the emotions and how psychological health intervention can be translated into computer methods. This research focuses on three elements that could foster behaviour change in individuals: the physical and emotional status of the person, and the technology. Every component can influence the user's attitude and behaviour in the following ways: ' Physical status: bad physical status could change human attitude toward the necessity to adopt health behaviours; at the same time, good health status reduces the need to adopt healthy habits. ' Emotional status: the attitude has an affective component, negative emotional state can reduce the ability of a person to adopt new behaviours, and mental well being is the ideal situation in which individuals have a predisposition to adopt healthy behaviours. ' Technology: it can help users to adopt new behaviours and can also be support to promote physical and emotional status. Following this approach the idea driven in this research is that technology that is designed to improve the physical status and the emotional status of the individual could better foster behaviour change. According to this principle, the Well.Be.Sign framework has been proposed. The framework is based on three views: ' The theoretical framework: it represents the patterns that have to be defined to design the technologies to promote well being. ' The influence diagram: it shows the persuasive forces in the context of health care. The role of the persuasive technologies is contextualized in a wider universe where other factors and persuasive forces influence a patient. ' The design process: it shows the process of design using an iterative, incremental methodology that applies a combination of existing methodologies (Goal Directed Design and Persuasive System Design) and others that are original to this research. The methods have been applied to design a system to deliver cardio rehabilitation at home: first a prototype has been defined according to the user’s needs, then it has been extended with the specific intervention required for the cardio–rehabilitation, finally the system has been developed and validated in a controlled clinical study in which the cardiovascular fitness, the level of knowledge, the perception of the illness, the persistence of healthy habits and the system acceptance (only the intervention group) were measured. The results show that the intervention group increased cardiovascular capacity, knowledge, feeling of control of illness and perceived benefits of exercise at the end of the study. After six months of the study, a followSup of the exercise habits was performed. Some individuals of the intervention group continued to be engaged in the running exercise sessions promoted in the designed system. Two other cases have been presented to demonstrate the foundations of the Well.Be.Sign’s approach to promote both physical and emotional status: ' People affected by Heart Failure, in which a bidirectional connection between health status and emotions has been discussed with patients. Two correlations were demonstrated: the relationship between symptoms and negative emotional response, and that negative emotional status is correlated with worsening of chronic conditions. ' People with mood disorders: the study shows that emotions could also impact how the user perceives the technology.