KeeLoq: Attacks and Example - Revision history

NKirnbauer: NKirnbauer moved page KeeLoq: Attacks to KeeLoq: Attacks and Example

2024-10-22T17:32:18Z

NKirnbauer moved page KeeLoq: Attacks to KeeLoq: Attacks and Example

← Older revision	Revision as of 17:32, 22 October 2024
(No difference)

NKirnbauer: merging similar articles

2024-10-22T17:31:27Z

merging similar articles

Show changes

NKirnbauer: NKirnbauer moved page KeeLoq Remake to KeeLoq: Attacks

2024-10-22T17:24:00Z

NKirnbauer moved page KeeLoq Remake to KeeLoq: Attacks

← Older revision	Revision as of 17:24, 22 October 2024
(No difference)

NKirnbauer: gendering, misspellings

2024-08-23T09:02:36Z

gendering, misspellings

← Older revision		Revision as of 09:02, 23 August 2024
Line 26:		Line 26:
	=== Slide Attack ===		=== Slide Attack ===

	The first slide attack found, was the work of Bodganov in 2007, which was the first paper describe and cryptoanalyze the KeeLoq block cipher. As stated already previously, ~~his~~ attack is based on a self similar key schedule, relative short block length (32 bit) and the fact that an efficient linear approximation of the NLF exists. Through the property of the slide attack, the computational complexity is independent from the number of encryption cycles. The attack carried out can be split into three main steps. A sliding step calculating the first bits k0 .. k15, a correlation step determining k47 .. k16 and the remaining bits k15 .. k0 by a linear step. The recovery complexity of ~~his~~ attack is about 252 computational steps and requires 232 plaintext-ciphertext pairs and 232 32 bit words (~17 GByte) in memory.		The first slide attack found, was the work of Bodganov in 2007, which was the first paper describe and cryptoanalyze the KeeLoq block cipher. As stated already previously, this attack is based on a self similar key schedule, relative short block length (32 bit) and the fact that an efficient linear approximation of the NLF exists. Through the property of the slide attack, the computational complexity is independent from the number of encryption cycles. The attack carried out can be split into three main steps. A sliding step calculating the first bits k0 .. k15, a correlation step determining k47 .. k16 and the remaining bits k15 .. k0 by a linear step. The recovery complexity of this attack is about 252 computational steps and requires 232 plaintext-ciphertext pairs and 232 32 bit words (~17 GByte) in memory.

	=== Power Analyses ===		=== Power Analyses ===
Line 37:		Line 37:
	; Cloning a Transmitter without Physical Access : Knowing k<sub>man</sub> and the key derivation method, enables an attacker to copy a remote from a distance. While the previous methods must be carried out from a specialist, this attack can be carried out by a non skilled person just using a hacking device built from a criminal cryptographer, that automatically recovers k<sub>dev</sub> and opens the target.		; Cloning a Transmitter without Physical Access : Knowing k<sub>man</sub> and the key derivation method, enables an attacker to copy a remote from a distance. While the previous methods must be carried out from a specialist, this attack can be carried out by a non skilled person just using a hacking device built from a criminal cryptographer, that automatically recovers k<sub>dev</sub> and opens the target.

	; Denial of Service : As explained in section "Authentication Protocols", the counters of receiver and transmitter have to be synchronized, to execute the function pressed on the remote. If an attacker possesses a cloned remote by one of the attacks mentioned above, ~~he is~~ also able to set the counter to the maximum of the re-synchronization window. After sending more valid hopping codes using the cloned and optimized remote, the receiver synchronizes with the counter value of the pirate device which renders the original remote useless, unless the owner of the original remote presses the button 2<sup>15</sup> times.		; Denial of Service : As explained in section "Authentication Protocols", the counters of receiver and transmitter have to be synchronized, to execute the function pressed on the remote. If an attacker possesses a cloned remote by one of the attacks mentioned above, they are also able to set the counter to the maximum of the re-synchronization window. After sending more valid hopping codes using the cloned and optimized remote, the receiver synchronizes with the counter value of the pirate device which renders the original remote useless, unless the owner of the original remote presses the button 2<sup>15</sup> times.
	In 2009 about the same team presented another attack based on SPA (Simple Power Analyses) which is more efficient and able to recover k<sub>man</sub> with a single power trace. The computation of the keys does not even require any knowledge about the inputs (clear text) or outputs (cipher text), instead all information can be derived from the power measurements.		In 2009 about the same team presented another attack based on SPA (Simple Power Analyses) which is more efficient and able to recover k<sub>man</sub> with a single power trace. The computation of the keys does not even require any knowledge about the inputs (clear text) or outputs (cipher text), instead all information can be derived from the power measurements.

MLindner at 20:40, 8 January 2024

2024-01-08T20:40:49Z

← Older revision		Revision as of 20:40, 8 January 2024
Line 15:		Line 15:
	[[File:Hopping_Code_Message_Format.png\|thumb\|Hopping Code Message Format]]		[[File:Hopping_Code_Message_Format.png\|thumb\|Hopping Code Message Format]]
	[[File:Hopping_Code_Windows.png\|thumb\|Hopping Code Synchronization Window]]		[[File:Hopping_Code_Windows.png\|thumb\|Hopping Code Synchronization Window]]
	This section discusses two authentication protocols, which both have KeeLoq algorithm involved. A simple bidirectional challenge-response protocol, used in identify-friend-foe (IFF) systems, were the transponder and receiver both share the same 64 bit key k. To authenticate the decoder sends a 32 bit random challenge to the transponder, which needs to respond with the challenge encrypted using k. After the decoder decrypted and compared the response with the original challenge successfully the device is authenticated. The other, in practice more often used, code-hopping (or rolling code) mode is a unidirectional protocol, which has the advantage that the remote device, which is naturally limited in power, never listens to the radio channel. Since first remote key-less entry systems had a fixed code, configurable with jumper settings, which was an easy target for replay attacks, the rolling code was invented to guard against such an easy attack. In principle it is a 16 bit counter value, stored on the remote device, which is concatenated with a discrimination value and four function bits, then encrypted. Remotes serial number has to be in clear text and is appended including a copy of the function bits and some flag bits. Every time a function button on the remote device is pressed the counter gets incremented. The receiver will decode the message and compare the counter ''cnt'' with its own synchronization counter, which is incremented every time a message is received and successfully decoded. The receiver first compares the serial number to its list of paired devices, and picks the corresponding key k<sub>dev</sub> and decodes the message.		This section discusses two authentication protocols, which both have KeeLoq algorithm involved. A simple bidirectional challenge-response protocol, used in identify-friend-foe (IFF) systems, were the transponder and receiver both share the same 64 bit key k. To authenticate the decoder sends a 32 bit random challenge to the transponder, which needs to respond with the challenge encrypted using k. After the decoder decrypted and compared the response with the original challenge successfully the device is authenticated. The other, in practice more often used, code-hopping (or rolling code) mode is a unidirectional protocol, which has the advantage that the remote device, which is naturally limited in power, never listens to the radio channel. Since first remote key-less entry systems had a fixed code, configurable with jumper settings, which was an easy target for replay attacks, the rolling code was invented to guard against such an easy attack. In principle it is a 16 bit counter value, stored on the remote device, which is concatenated with a discrimination value and four function bits, then encrypted. By modifying a single input bit, the so-called Avalanche Effect guarantees, that at least half of the output bits are changed as well. Remotes serial number has to be in clear text and is appended including a copy of the function bits and some flag bits. Every time a function button on the remote device is pressed the counter gets incremented. The receiver will decode the message and compare the counter ''cnt'' with its own synchronization counter, which is incremented every time a message is received and successfully decoded. The receiver first compares the serial number to its list of paired devices, and picks the corresponding key k<sub>dev</sub> and decodes the message.

	If the decoded value of the synchronization counter is within the open window, the receiver executes the function and sets its synchronization counter to the last value received. Is the received value in the re-synchronization window, the remote has to send another message with a subsequent <sub>cnt</sub> value. This is for the case the remote was be pressed accidentally without being in range of the receiver. In that case the remotes function button has to be pressed again. If the received <sub>cnt</sub> value is in the blocked window, function will not be executed at all.		If the decoded value of the synchronization counter is within the open window, the receiver executes the function and sets its synchronization counter to the last value received. Is the received value in the re-synchronization window, the remote has to send another message with a subsequent <sub>cnt</sub> value. This is for the case the remote was be pressed accidentally without being in range of the receiver. In that case the remotes function button has to be pressed again. If the received <sub>cnt</sub> value is in the blocked window, function will not be executed at all.
Line 55:		Line 55:

	* “Drive it like you hacked it: New attacks and tools to wirelessly steal cars,” 2015. [Online]. Available: https://www.defcon.org/html/defcon-23/dc-23-speakers.html#Kamkar		* “Drive it like you hacked it: New attacks and tools to wirelessly steal cars,” 2015. [Online]. Available: https://www.defcon.org/html/defcon-23/dc-23-speakers.html#Kamkar
			* Yue-li Hu, Yan Zhang, and Bin Sun. Design of rke system based on keeloq encryption technology. In 2009 International Conference on Artificial Intelligence and Computational Intelligence, volume 1, pages 324–327, 2009


	[[Category:Basic]]		[[Category:Basic]]

REichinger: /* Power Analyses */

2020-12-19T15:03:53Z

Power Analyses

← Older revision		Revision as of 15:03, 19 December 2020
Line 31:		Line 31:
	The next attack, from the work of Eisenbarth, was published in 2008 as the first successful DPA (Differnential Power Analyses) attack on KeeLoq. They presented in their work three key recovery attacks, which allow someone to reveal the secret key from the transmitter, and if a weak key derivation method was used, also the manufacturer key stored on the receiver, which enables key cloning. Also this attack is suitable to target both modes, IFF and hopping code. Based on their work they presented four attack methods with more or less implications on the real world:		The next attack, from the work of Eisenbarth, was published in 2008 as the first successful DPA (Differnential Power Analyses) attack on KeeLoq. They presented in their work three key recovery attacks, which allow someone to reveal the secret key from the transmitter, and if a weak key derivation method was used, also the manufacturer key stored on the receiver, which enables key cloning. Also this attack is suitable to target both modes, IFF and hopping code. Based on their work they presented four attack methods with more or less implications on the real world:

	; Cloning a Transmitter : An attacker needs access to the transmitter and the time to take about 10 to 30 power traces. Once k<sub>dev</sub> is revealed, the messages can be decrypted and read out and with that values~~\footnote{~~serial number, counter and discrimination value of the master} a copy of the remote can be produced.		; Cloning a Transmitter : An attacker needs access to the transmitter and the time to take about 10 to 30 power traces. Once k<sub>dev</sub> is revealed, the messages can be decrypted and read out and with that values (serial number, counter and discrimination value of the master) a copy of the remote can be produced.

	; Recover Manufacturer Key : Requires physical access to one receiver of that manufacturer and several thousands power traces. Knowing k<sub>man</sub> someone can produce valid device keys, which are not able open anything, since they must first be paired with a receiver device. But this key recovery method is relevant in the context of product piracy.		; Recover Manufacturer Key : Requires physical access to one receiver of that manufacturer and several thousands power traces. Knowing k<sub>man</sub> someone can produce valid device keys, which are not able open anything, since they must first be paired with a receiver device. But this key recovery method is relevant in the context of product piracy.

REichinger: /* Power Analyses */

2020-12-19T15:01:52Z

Power Analyses

← Older revision		Revision as of 15:01, 19 December 2020
Line 31:		Line 31:
	The next attack, from the work of Eisenbarth, was published in 2008 as the first successful DPA (Differnential Power Analyses) attack on KeeLoq. They presented in their work three key recovery attacks, which allow someone to reveal the secret key from the transmitter, and if a weak key derivation method was used, also the manufacturer key stored on the receiver, which enables key cloning. Also this attack is suitable to target both modes, IFF and hopping code. Based on their work they presented four attack methods with more or less implications on the real world:		The next attack, from the work of Eisenbarth, was published in 2008 as the first successful DPA (Differnential Power Analyses) attack on KeeLoq. They presented in their work three key recovery attacks, which allow someone to reveal the secret key from the transmitter, and if a weak key derivation method was used, also the manufacturer key stored on the receiver, which enables key cloning. Also this attack is suitable to target both modes, IFF and hopping code. Based on their work they presented four attack methods with more or less implications on the real world:

	; Cloning a Transmitter : An attacker needs access to the transmitter and the time to take about 10 to 30 power traces. Once k~~\textsubscript{~~dev} is revealed, the messages can be decrypted and read out and with that values\footnote{serial number, counter and discrimination value of the master} a copy of the remote can be produced.		; Cloning a Transmitter : An attacker needs access to the transmitter and the time to take about 10 to 30 power traces. Once k<sub>dev</sub> is revealed, the messages can be decrypted and read out and with that values\footnote{serial number, counter and discrimination value of the master} a copy of the remote can be produced.

	; Recover Manufacturer Key : Requires physical access to one receiver of that manufacturer and several thousands power traces. Knowing k~~\textsubscript{~~man} someone can produce valid device keys, which are not able open anything, since they must first be paired with a receiver device. But this key recovery method is relevant in the context of product piracy.		; Recover Manufacturer Key : Requires physical access to one receiver of that manufacturer and several thousands power traces. Knowing k<sub>man</sub> someone can produce valid device keys, which are not able open anything, since they must first be paired with a receiver device. But this key recovery method is relevant in the context of product piracy.

	; Cloning a Transmitter without Physical Access : Knowing k<sub>man</sub> and the key derivation method, enables an attacker to copy a remote from a distance. While the previous methods must be carried out from a specialist, this attack can be carried out by a non skilled person just using a hacking device built from a criminal cryptographer, that automatically recovers k<sub>dev</sub> and opens the target.		; Cloning a Transmitter without Physical Access : Knowing k<sub>man</sub> and the key derivation method, enables an attacker to copy a remote from a distance. While the previous methods must be carried out from a specialist, this attack can be carried out by a non skilled person just using a hacking device built from a criminal cryptographer, that automatically recovers k<sub>dev</sub> and opens the target.

REichinger: /* Power Analyses */

2020-12-19T15:00:18Z

Power Analyses

← Older revision		Revision as of 15:00, 19 December 2020
Line 29:		Line 29:

	=== Power Analyses ===		=== Power Analyses ===
	The next attack, ~~described in this paper \cite{PowerAnalysis}~~ was published in 2008 as the first successful DPA (Differnential Power Analyses) attack on KeeLoq. They presented in their work three key recovery attacks, which allow someone to reveal the secret key from the transmitter, and if a weak key derivation method was used, also the manufacturer key stored on the receiver, which enables key cloning. Also this attack is suitable to target both modes, IFF and hopping code. Based on their work they presented four attack methods with more or less implications on the real world:		The next attack, from the work of Eisenbarth, was published in 2008 as the first successful DPA (Differnential Power Analyses) attack on KeeLoq. They presented in their work three key recovery attacks, which allow someone to reveal the secret key from the transmitter, and if a weak key derivation method was used, also the manufacturer key stored on the receiver, which enables key cloning. Also this attack is suitable to target both modes, IFF and hopping code. Based on their work they presented four attack methods with more or less implications on the real world:

	; Cloning a Transmitter : An attacker needs access to the transmitter and the time to take about 10 to 30 power traces. Once k\textsubscript{dev} is revealed, the messages can be decrypted and read out and with that values\footnote{serial number, counter and discrimination value of the master} a copy of the remote can be produced.		; Cloning a Transmitter : An attacker needs access to the transmitter and the time to take about 10 to 30 power traces. Once k\textsubscript{dev} is revealed, the messages can be decrypted and read out and with that values\footnote{serial number, counter and discrimination value of the master} a copy of the remote can be produced.

REichinger: /* Introduction */

2020-12-19T14:46:28Z

Introduction

← Older revision		Revision as of 14:46, 19 December 2020
Line 1:		Line 1:
	== Introduction ==		== Introduction ==
	KeeLoq was invented at Nanoteq (South Africa) in the 1980's by Frederick Bruwer (uni-directional command transfer protocol), Gideon Kuhn (cryptographic algorithm) and Willem Smit (silicon implementation). The specifications of KeeLoq are patented and can only be used under license. In November 1995 Microchip ~~Technologie~~ Inc. acquired the KeeLoq code hopping technology patents along with the worldwide marketing rights. Typical applications for the KeeLoq encoders and decoders include remote keyless entry (RKE) systems, alarm systems, immobilizers, car alarms, garage door openers, burglar alarms, secure communications such as in smoke/carbon monoxide/radon detectors, remote-control toys, model cars/airplanes, appliances, identity tokens and tracking of parts/packages. Also allows KeeLoq block cipher a low cost hardware implementation with low power consumption. Having such a broad field of application, also mainly in security related topics, KeeLoq became interesting for researchers, as well criminals all over the world. After releasing implementation details on a Russian website in 2006, first successful attacks on the algorithm are published in 2007, were the weakness of self similarity of the key schedule, combined with a quite short key length, allowed to mount a slide attack.		KeeLoq was invented at Nanoteq (South Africa) in the 1980's by Frederick Bruwer (uni-directional command transfer protocol), Gideon Kuhn (cryptographic algorithm) and Willem Smit (silicon implementation). The specifications of KeeLoq are patented and can only be used under license. In November 1995 Microchip Technology Inc. acquired the KeeLoq code hopping technology patents along with the worldwide marketing rights. Typical applications for the KeeLoq encoders and decoders include remote keyless entry (RKE) systems, alarm systems, immobilizers, car alarms, garage door openers, burglar alarms, secure communications such as in smoke/carbon monoxide/radon detectors, remote-control toys, model cars/airplanes, appliances, identity tokens and tracking of parts/packages. Also allows KeeLoq block cipher a low cost hardware implementation with low power consumption. Having such a broad field of application, also mainly in security related topics, KeeLoq became interesting for researchers, as well criminals all over the world. After releasing implementation details on a Russian website in 2006, first successful attacks on the algorithm are published in 2007, were the weakness of self similarity of the key schedule, combined with a quite short key length, allowed to mount a slide attack.
	Over the years many flavours of attack strategies got developed, from attacking the cipher directly using mathematical methods, or the protocol using replay or man-in-the-middle attacks. Also the implementation offers attack vectors using side-channel-attack methods by measuring power consumption, temperature, electromagnetic fields on the chips or by measuring response times. The weaknesses within KeeLoq and its implementation will be presented in this document.		Over the years many flavours of attack strategies got developed, from attacking the cipher directly using mathematical methods, or the protocol using replay or man-in-the-middle attacks. Also the implementation offers attack vectors using side-channel-attack methods by measuring power consumption, temperature, electromagnetic fields on the chips or by measuring response times. The weaknesses within KeeLoq and its implementation will be presented in this document.

REichinger: REichinger moved page NewKeeLoq to KeeLoq Remake: to find the page below 'K', instead of 'N'

2020-12-19T14:39:57Z

REichinger moved page NewKeeLoq to KeeLoq Remake: to find the page below 'K', instead of 'N'

← Older revision	Revision as of 14:39, 19 December 2020
(No difference)