Karthikeyan Bhargavan
email: karthikeyan.bhargavan@inria.fr

Gaëtan Leurent
email: gaetan.leurent@inria.fr

On the Practical (In-)Security of 64-bit Block Ciphers Collision Attacks on HTTP over TLS and OpenVPN

While modern block ciphers, such as AES, have a block size of at least 128 bits, there are many 64-bit block ciphers, such as 3DES and Blowfish, that are still widely supported in Internet security protocols such as TLS, SSH, and IPsec. When used in CBC mode, these ciphers are known to be susceptible to collision attacks when they are used to encrypt around 2 32 blocks of data (the so-called birthday bound). This threat has traditionally been dismissed as impractical since it requires some prior knowledge of the plaintext and even then, it only leaks a few secret bits per gigabyte. Indeed, practical collision attacks have never been demonstrated against any mainstream security protocol, leading to the continued use of 64-bit ciphers on the Internet.

In this work, we demonstrate two concrete attacks that exploit collisions on short block ciphers. First, we present an attack on the use of 3DES in HTTPS that can be used to recover a secret session cookie. Second, we show how a similar attack on Blowfish can be used to recover HTTP BasicAuth credentials sent over OpenVPN connections. In our proof-of-concept demos, the attacker needs to capture about 785GB of data, which takes between 19-38 hours in our setting. This complexity is comparable to the recent RC4 attacks on TLS: the only fully implemented attack takes 75 hours. We evaluate the impact of our attacks by measuring the use of 64-bit block ciphers in real-world protocols. We discuss mitigations, such as disabling all 64-bit block ciphers, and report on the response of various software vendors to our responsible disclosure of these attacks.

INTRODUCTION

Internet protocols such as TLS [START_REF] Dierks | The Transport Layer Security (TLS) Protocol Version 1.2[END_REF], SSH [START_REF] Ylonen | The Secure Shell (SSH) Transport Layer Protocol[END_REF], and IPsec [START_REF] Frankel | IP Security (IPsec) and Internet Key Exchange (IKE) Document Roadmap[END_REF] are agile, in the sense that they are designed to support a wide variety of ciphersuites: combinations of key exchange protocols, encryption schemes, authentication modes, etc. Each protocol implementation may choose to support a different subset of ciphersuites, but two implementations can still interoperate if they can negotiate a common cipher-Figure 1: The Beastly attacker model for HTTPS: A network attacker injects JavaScript on some window in the user's browser, which then makes cross-origin HTTPS requests to a target website. The browser attaches a secret cookie or HTTP BasicAuth password to authenticate each request. The attacker observes the encrypted traffic stream and tries to recover the secret.

suite. When it works well, protocol agility can enable a graceful transition from old cryptographic algorithms to new ones. A server can, for example, offer AES-GCM to modern clients while still supporting legacy ciphers like 3DES for older clients that have not yet been upgraded. However, a negative consequence of agility is that old ciphers may never be removed, resulting in implementations that support a few strong modern ciphers, followed by a long tail of obsolete ciphers that are still supported for backwards compatibility, but are known to be cryptographically weak. For example, the OpenSSL library supports five versions of TLS and hundreds of ciphersuites, even though many of these ciphersuites include weak algorithms like RC4 and MD5.

There are several reasons why practitioners do not consider theoretical weaknesses in cryptographic to be sufficient for their removal from mainstream protocols. First, even if an obsolete primitive is supported, it will typically only be negotiated if one of the parties does not support a modern alternative, in which case, the obsolete cipher is still better than nothing. Second, the attack may not be applicable to the way the primitive is used in the protocol, or it may require too much computation to be considered practical. Third, the attack may require special knowledge about the structure or the content of the plaintext stream which may be difficult to obtain in general. Consequently, protocol implementations tend to support legacy ciphers until a concrete attack is demonstrated in a common usage of the protocol.

Attacks on Legacy Crypto. A series of recent attacks on TLS have conclusively shown that this line of defense for legacy ciphers is fatally flawed. Leaving old protocol versions and obsolete cryptographic algorithms enabled can lead to devastating attacks, such as BEAST [START_REF] Duong | Here come the ⊕ ninjas[END_REF] (on CBC encryption in TLS 1.0), CRIME [START_REF] Rizzo | The crime attack[END_REF] (on TLS compression), Lucky13 [START_REF] Alfardan | Lucky thirteen: Breaking the TLS and DTLS record protocols[END_REF] (on CBC padding in TLS 1.2), POODLE [START_REF] Bodo Moller | This POODLE Bites: Exploiting The SSL 3.0 Fallback[END_REF] (on CBC padding in SSL 3.0), RC4 NOMORE [START_REF] Alfardan | On the Security of RC4 in TLS[END_REF][START_REF] Garman | Attacks Only Get Better: Password Recovery Attacks Against RC4 in TLS[END_REF][START_REF] Vanhoef | All Your Biases Belong to Us: Breaking RC4 in WPA-TKIP and TLS[END_REF] (on keystream biases in RC4), FREAK [START_REF] Beurdouche | A messy state of the union: Taming the composite state machines of TLS[END_REF] (on export-grade RSA keys), Logjam [START_REF] Adrian | Imperfect forward secrecy: How Diffie-Hellman fails in practice[END_REF] (on export-grade Diffie-Hellman groups), SLOTH [START_REF] Bhargavan | Transcript Collision Attacks: Breaking Authentication in TLS, IKE, and SSH[END_REF] (on MD5 signatures), and DROWN [START_REF] Aviram | DROWN: Breaking TLS using SSLv2[END_REF] (on RSA-PKCS#1v1.5 encryption in SSL 2.0). These attacks follow a common pattern. Each attack is based on a classic cryptographic weakness that was known to cryptographers for years or even decades in advance, but had not been demonstrated in real-world TLS scenarios. So these works showed that with modern network speeds and computing power, the computational effort required to exploit the theoretical weakness is feasible even for academic researchers. Furthermore, many of these attacks (e.g. BEAST, CRIME, RC4 NOMORE) can be made more efficient by relying on a new HTTPS attacker model introduced by BEAST. Figure 1 depicts this Beastly attacker model, where a network attacker uses JavaScript to implement an adaptive chosen-plaintext adversary who can mix in his plaintext with the user's secret values, and then use his network vantage point to actively or passively attack the ciphertext.

The final element of each attack is finding clients and servers who are willing to negotiate the legacy cipher. Some of the attacked algorithms (e.g. RC4) and protocol versions (e.g. SSL 3.0) were highly popular before the attack and have since been deprecated. Other weak algorithms (e.g. export ciphers) and versions (e.g. SSL 2.0) had already been deprecated years ago and were never expected to be negotiated between modern clients and servers. Surprisingly however, in many cases the attacker is able to force the negotiation of a weak algorithm via a downgrade attack by exploiting protocol flaws (e.g. Logjam, SLOTH) or implementation bugs (e.g. FREAK, DROWN). One lesson to take from these downgrade attacks is that relying on the negotiation protocol to avoid legacy ciphers is error-prone and dangerous. When a concrete attack against a legacy cipher is discovered, the only safe mitigation is to fully remove the weak cipher from all implementations.

These previous attacks evaluated a variety of obsolete cryptographic constructions and provided enough evidence of their dangers for them to be disabled in popular implementations. We believe that it is important for the research community to be vigilant and to continue to investigate the strength of the weakest ciphers still supported by mainstream protocols. For example, the attacks on RC4 have resulted in RC4 being removed as the default fallback cipher for TLS implementations, and this role has now fallen to 3DES, which is a 28 year old 64-bit block cipher with known weaknesses. However, the practical security of 64-bit block ciphers as used in TLS and other protocols has not been previously studied. This work aims to address this gap and to provide concrete attacks and firm guidance on the use of such ciphers.

Collision Attacks on 64-bit Block Ciphers. The security of a block cipher is often reduced to the key size k: the best attack should be the exhaustive search of the key, with complexity 2 k . However, the block size n is also an important security parameter, defining the amount of data that can be encrypted under the same key. This is particularly im-portant when using common modes of operation: we require block ciphers to be secure with up to 2 n queries, but most modes of operation (e.g. CBC, CTR, GCM, OCB, etc.) are unsafe with more than 2 n/2 blocks of message (the so-called birthday bound). In particular, when these many blocks are encrypted under a key in CBC mode, the probability of collisions between two ciphertext blocks becomes significant, and each ciphertext collision reveals the XOR of the two corresponding plaintext blocks from the stream. Consequently, if the attacker can guess one of the plaintext blocks, he can recover the plaintext in the other block. While this attack is well-known to researchers [START_REF] Rogaway | Evaluation of Some Blockcipher Modes of Operation[END_REF][START_REF] Mcgrew | Impossible plaintext cryptanalysis and probable-plaintext collision attacks of 64-bit block cipher modes[END_REF], it is often disregarded by practitioners because it require known plaintext, and reveals only a few bits of a large datastream.

With a modern block cipher with 128-bit blocks such as AES, the birthday bound corresponds to 256 EB (2 68 bytes). While this is leaves a safe margin for common uses of cryptography today, the resulting security is still lower than could be expected of 128-bit security and might be an issue in the future. As a point of comparison, Google is estimated to store around 16 EB (2 64 bytes), and the global Internet traffic is expected to reach 1 ZB (2 70 bytes) per year in 2016.

More strikingly, the birthday bound corresponds to only 32 GB for a block cipher with 64-bit blocks, and there are many real-world protocol scenarios in which this amount of data may be sent under a 64-bit cipher: e.g. 3G telephone connections (UMTS), which are encrypted with KASUMI, OpenVPN tunnels, which uses Blowfish as the default cipher, and Internet standards like TLS, SSH, and IPsec that use 3DES and Blowfish as legacy ciphers for interoperability. In all these scenarios, 32 GB of data can be transferred in less than one hour with a fast connection.

More recently, 64-bit ciphers have become common in the field of lightweight cryptography for applications, such as embedded systems and smart devices, where resources are too constrained to use conventional block ciphers. For instance, PRESENT [START_REF] Bogdanov | PRESENT: An ultra-lightweight block cipher[END_REF] and HIGHT [START_REF] Hong | HIGHT: A new block cipher suitable for low-resource device[END_REF] have been standardized by ISO recently (in ISO/IEC 29192 and ISO/IEC 18033-3, respectively).

Our Results. In this work, we study the concrete impact of birthday attacks against 64-bit block-ciphers as used in popular protocols. We present the first concrete attacks based on ciphertext collisions on mainstream Internet protocols.

We focus on two concrete use cases. First, we consider the use of OpenVPN to secure HTTP connections between a web browser and a website, where the website asks the user for HTTP BasicAuth (user/password) authentication. OpenVPN uses Blowfish in CBC mode by default, and we show how one can use the Beastly attacker scenario to generate a lot of traffic including the BasicAuth in every request, until collisions collisions in the Blowfish ciphertext reveal the BasicAuth token (i.e. the password). We demonstrate a proof-of-concept attack between a Firefox client and an nginx server connected via OpenVPN. The attack requires about 785GB, which takes 19 hours in our setting to recover the 16-byte authorization token.

Second, we consider the use of TLS to secure HTTP connections between a browser and an HTTPS website that sets secure session cookies on the browser. We find that 3DES is supported by nearly 90% of HTTPS servers and by all mainstream TLS clients. In practice, however, 3DES is less preferred than AES and negotiated by only 1-2% of HTTPS connections. For such connections, we demonstrate an attack, again using the Beastly attacker setup, that can recover the secret 16-byte session cookie sent by the browser with every HTTPS request to the target server. We demonstrate the attack between a Firefox browser and an IIS 6.0 server (Windows Server 2003 R2 SP2), both in their default up-to-date configuration. This attack also requires 785GB, which takes 38 hours in our setting.

Our attacks demonstrate that collision-based attacks on 64-bit block ciphers are practically exploitable. We suggest two mitigations for the attack. Considering the low negotiation probability of 3DES in TLS, we recommend disabling it in popular clients and servers. For protocols where 64bit ciphers cannot yet be deprecated, we recommend using strict rekeying limits to mitigate the attack. In response to our attacks, mainstream TLS libraries, web browsers, and OpenVPN have begun implementing these mitigations.

Outline. Section 2 provides background on collision attacks on block ciphers and estimates their success probability under various conditions. Section 3 investigates the usage of 64bit ciphers in various Internet protocols, and specifically in HTTPS. Section 4 shows how block cipher collisions in the encrypted stream can be used to attack HTTP. Section 4.4 and 4.5 describe our proof-of-concept attacks on OpenVPN and HTTPS, respectively. Section 5 discusses the impact of our attacks and their mitigations.

COLLISION ATTACKS ON BLOCK CI-PHERS

Block ciphers like AES and 3DES are widely used for symmetric encryption in security protocols. Mathematically, a block cipher with a κ-bit key and n-bit blocks defines of family of permutations of n-bit strings, indexed by the key. The main security notion is that a block cipher should behave like a pseudo-random permutation (PRP) family: the block cipher E k with a random key k should be hard to distinguish from a random permutation.

Block ciphers operate on blocks of fixed size, n bits, usually with n = 64 (DES, 3DES, Blowfish, IDEA, KASUMI, PRESENT, ...) or n = 128 (AES, Camellia, Twofish, Serpent, SEED, ...). In order to deal with arbitrary-length messages, they are used within a mode of operation. A mode divides the message M into n-bit blocks mi, and process the blocks one by one through the block cipher E with various chaining rules, to produce ciphertext blocks ci and/or an authentication tag τ . Several modes have been widely studied and standardized [START_REF] Dworkin | Recommendation for Block Cipher Modes of Operation[END_REF] for encryption (CBC, CFB, OFB, CTR), authentication (CBC-MAC, PMAC) and authenticated encryption (OCB, CCM, GCM).

Security at the Birthday Bound

While block ciphers are required to resist any attack with up to 2 n data and 2 κ time, most modes of operation are only proven secure up to 2 n/2 blocks of plaintext, a limit that is commonly called the birthday bound. Indeed, there are attacks matching this limit. In CBC mode, the probability of collisions between two n-bit ciphertext blocks becomes significant after 2 n/2 blocks because of the birthday paradox. Rogaway summarizes the situation as follows [30, page 36]:

In general, unless special efforts are taken, almost any mode of operation based on an n-bit block- Do birthday-bound attacks on CBC, CFB, and OFB actually matter? They are of relatively little concern when the blockcipher has a blocksize of n = 128 bits, but the attacks can be a serious concern when employing a blockcipher of n = 64 bits, requiring relatively frequent rekeying to keep σ 2 32 .

c (0) -1 = IV m (0) 0 E k c (0) 0 m (0) 1 E k c (0) 1 m (0) 2 E k c (0) 2 m (0) 3 E k c (0) 3
More recently, McGrew investigated plaintext recovery attacks on 64-bit ciphers in CBC, CFB, and CTR modes. He studied the mount of information leakage by assuming that the attacker can observe all the ciphertext in an encrypted stream and he has some (incomplete) knowledge of the plaintext [START_REF] Mcgrew | Impossible plaintext cryptanalysis and probable-plaintext collision attacks of 64-bit block cipher modes[END_REF]. This theoretical analysis resulted in new security recommendations for IPsec [START_REF] Mcgrew | Cryptographic Algorithm Implementation Requirements and Usage Guidance for Encapsulating Security Payload (ESP) and Authentication Header (AH)[END_REF], but they did not trigger any significant changes in mainstream deployments of 64-bit ciphers in IPsec, TLS, or SSH. Arguably the main reason for the limited impact of these attacks is that they were never implemented against a popular protocol under real-world conditions.

Following McGrew, we explain theoretical attacks against the CBC and CTR modes (the two most widely used encryption modes) in more detail below. In the rest of the paper, we will show that these attacks can be exploited to mount concrete attacks on HTTP over TLS and OpenVPN.

Plaintext recovery attack against CBC

The CBC mode is one of the oldest encryption modes, and still widely used. The message M is divided into blocks mi, 0 ≤ i < (see Figure 2) and is encrypted as:

ci = E k (mi ⊕ ci-1),
where c-1 is an initialization value usually denoted as IV. For simplicity, here we assume that all message sizes are a multiple of the block size.

When encrypting a sequence of messages M (j) , each message should be encrypted with a fresh random IV c (j) -1 . It is important that the IV can not be predicted by an adversary who can encrypt chosen messages; otherwise, it can lead to attacks, as first observed by Rogaway in 1995 [START_REF] Rogaway | Problems with Proposed IP Cryptography[END_REF], and subsequently exploited in the BEAST attack [START_REF] Duong | Here come the ⊕ ninjas[END_REF] in 2011 on TLS versions prior to 1.1.

CBC has been proven secure up to 2 n/2 blocks of messages [START_REF] Bellare | The security of cipher block chaining[END_REF][START_REF] Petrank | CBC MAC for real-time data sources[END_REF]. On the other hand there is a simple birthday attack against CBC: after 2 n/2 message blocks encrypted with the same key (in the same message or in different messages), a collision between two ciphertext blocks c (j) i = c (j ) i is expected. Since E k is a permutation, a collision in the output means that the inputs are the same (m

(j) i ⊕ c (j) i-1 = m (j ) i ⊕ c (j ) i -1
), which reveals the xor of two plaintext blocks:

m (j) i ⊕ m (j ) i = c (j) i-1 ⊕ c (j ) i -1 .
Success probability. In general, with 2 d blocks of data, the probability that there is at least one collision is (using

D = 2 d and N = 2 n ): p = 1 - D-1 i=0 N -i N ≥ 1 - D-1 i=0 e -i/N using 1 -x ≤ e -x ≥ 1 -e -D(D-1)/2N
In particular, with d > n/2, we have p ≥ 1 -e -1/2 ≈ 0.39. With larger values of d, the probably grows very close to 1:

p ≥ 1 - 2N D(D -1) + 2N using 1 -e -x > x x + 1 ≥ 1 - 2N D 2 since D 2 < D(D -1) + 2N p ≥ 1 -2 n-2d+1
On the other hand, when d < n/2 we can use:

p ≥ D(D -1) 4N ≈ 2 2d-n-2 using e -x < 1 -x/2
Furthermore, with 2 d blocks of data the expected number of collisions is roughly 2 2d-n-1 .

Distinguishing attack against CTR

The counter mode CTR is another popular mode of operation for encryption, first proposed by Diffie and Hellman [START_REF] Diffie | Privacy and authentication: An introduction to cryptography[END_REF]. In particular, it provides the encryption part of authenticated encryption modes CCM and GCM, and a variant of counter mode is used in 3G telephony (f8). The counter mode actually builds a stream cipher out of a block cipher: a counter is encrypted to generate key-stream that is xored with the message. More precisely, the message M is divided into blocks mi, 0 ≤ i < which are encrypted as:

ci = E k (IV + i) ⊕ mi,
where IV is the initial value of the counter (see Figure 3).

If the encryption function E k is a pseudo-random function, rather than a pseudo-random permutation, then CTR is secure up to 2 n blocks [START_REF] Bellare | A concrete security treatment of symmetric encryption[END_REF]. However, in the common case where E k is a permutation, CTR is proven secure only up to 2 n/2 blocks, and there is matching distinguishing attack with complexity 2 n/2 . If a message where all the plaintext blocks are equal is encrypted, then all the ciphertext blocks will be pairwise different. Indeed, all the E k (IV + i) are unique, because E k is a permutation. This enables the attacker to distinguish the counter mode from an ideal encryption scheme, because a collision between two ciphertext blocks becomes likely (with probability about 0.39). More interestingly, if the attacker has prior knowledge about the plaintext (such as a IV + 0

E k p (0) 0 c (0) 0 IV + 1 E k p (0) 1 c (0) 1 IV + 2 E k p (0) 2 c (0) 2 IV + 3 E k p (0) 3 c (0) 3
Figure 3: CTR mode dictionary), he can use the distinguishing attack to eliminate impossible values to eventually guess the right plaintext [START_REF] Mcgrew | Impossible plaintext cryptanalysis and probable-plaintext collision attacks of 64-bit block cipher modes[END_REF].

It is interesting to compare the collision attacks against CBC and CTR. Both attacks have the same complexity, and show that the proofs are tight. However, the loss of security is quite different: an attacker can immediately recover some bits of information from the attack against CBC, while the attack against the counter mode requires a lot more work to recover any plaintext. In the remainder of this paper, we investigate on the practical impact of the CBC attack, but similar techniques (with higher complexity and more assumptions on the plaintext) may be used to attack CTR and GCM mode encryption in protocols like TLS and SSH.

Rekeying before the Birthday Bound

The main countermeasure against birthday attacks is to change the key frequently, before reaching the birthday bound under any single key. For instance, if the key is changed after 2 n/2-16 blocks, a birthday attack against a given only succeeds with probability 2 -32 , and an attacker has to collect 2 32 different sessions to mount an attack with high probability.

If implemented properly, this is an effective security measure to strengthen block ciphers with a small block-size. We stress than the key must be changed well before 2 n/2 blocks, despite misleading recommendations in published standards. For instance, ISO recommends [START_REF]On the Assessment of Cryptographic Techniques and Key Lengths[END_REF]:

Generally, for a block cipher with block size of n bits, the maximum amount of plaintext that can be encrypted before rekeying must take place is 2 (n/2) blocks, due to the birthday paradox. As long as the implementation of a specific block cipher do not exceed these limits, using the block cipher will be safe. This is incorrect, because collisions can be found with high probability (close to 0.39) with only 2 n/2 blocks. Indeed, we will show that our concrete attacks also work against connections that are rekeyed close to the birthday bound.

Towards a Practical Attack on CBC

The CBC attack reveals the xor of two plaintext block, and in many contexts, this may not be sufficient for a practical attack. However, an effective attack can be mounted when the following conditions are fulfilled: (1) some high-value secret data is sent repeatedly; and (2) some fraction of the plaintext is known. In this case, there is a chance that a collision leaks the xor between a valuable secret and a known block; this would immediately reveal the secret. More precisely, this attack is expected to succeed (i.e. to recover one block of a high-value secret) with high probability as soon as 2 s blocks of secret and 2 t known blocks are encrypted, with s + t ≥ n.

To mount the attack in practice, an adversary would collect and store all the traffic, then sort the ciphertext blocks to find collisions. Assuming that the adversary knows the position of the secret blocks and of the known blocks in the stream, he can quickly see which collisions are useful, and recover the secret values by xoring with the known plaintext.

Attack Complexity. Let us denote the known fraction of the data as α and the secret and valuable fraction of the traffic as β (with fraction 1 -α -β that is neither known nor valuable to the attacker). In order to recover some secret information, an attacker must collect roughly 1 /2αβ collisions, so that one collision is between a valuable secret block and a known block. Following the analysis of Section 2.2, this requires about 1 /αβ • 2 n/2 blocks of data.

For instance, with n = 64, in an optimal case for the adversary half of the traffic is known, and half of the traffic is highly valuable (α = β = 1/2). In this case, a collision an attack requires about:

1 /αβ • 2 n/2 = 2 • 2 n/2 = 2 33
blocks of data, which corresponds to just 64 GB. For a more concrete scenario, let us assume that the messages are HTTP queries of 512 bytes (64 blocs), with a secret 8-byte cookie (1 block), and that the remaining of the message is known, i.e. α = 63 /64 ≈ 1, β = 1 /64. The number of blocks needed by an attacker is roughly:

1 /αβ • 2 n/2 ≈ 8 • 2 n/2 = 2 35
which correspond to 256 GB.

Rekeying at the Birthday Bound. The attack can also be carried out when rekeying is used, if the keys are changed with low frequency. In particular, even if the keys are changed before 2 n/2 blocks are encrypted, there is still a non-negligible probability that a collision occurs.

More precisely, let us assume that keys are rotated after encrypting 2 r blocks (r ≤ n/2). As explained in Section 2.2, the probability to have a collision between 2 r blocks is at least 2 2r-n-2 . Therefore, an attacker needs 1 /2αβ • 2 n+2-2r sessions (i.e. 1 /2αβ • 2 n+2-r blocks) to collect an interesting collision. In practice, the attacker would collect all the data in a session, sort it to find collisions, and can discard the data before collecting data from the next session.

In an optimal setting for the attacker (α = β = 1/2), if the keys are changed after 2 n/2 blocks as recommended by ISO [START_REF]On the Assessment of Cryptographic Techniques and Key Lengths[END_REF] (r = n/2), the number of blocks needed by an attacker is roughly:

1 /2αβ • 2 n+2-r = 2 • 2 n/2+2 = 2 35
which correspond to 256 TB. In the HTTP example above, the number of blocks needed is roughly:

1 /2αβ • 2 n+2-r ≈ 32 • 2 n/2+2 = 2 39
which correspond to 4 TB. Therefore rekeying just before 2 n/2 blocks only has a limited impact on collision attacks.

Optimal Rekeying Strategies. The optimal use of rekeying has been studied by Abdalla and Bellare in [START_REF] Abdalla | Increasing the lifetime of a key: a comparative analysis of the security of re-keying techniques[END_REF], with the goal of increasing the encryption threshold (the number of blocks that can be encrypted before the advantage of an adversary becomes significant). Their result depend on the key size κ and the block size n. When n = κ, the optimal strategy is to rekey after 2 n/3 blocks, leading to an encryption threshold of 2 2n/3 (rather than 2 n/2 without rekeying). Concrete figures for AES-based modes are also given in [START_REF] Luykx | Limits on authenticated encryption use in TLS, march 2016[END_REF].

On the other hand, when κ ≥ 2n (as is the case for 3DES and Blowfish-128), the optimal strategy is to rekey for every block. Assuming a perfect rekeying function, this leads to an encryption threshold of 2 n (rather than 2 n/2 ). In actual protocols such as TLS or OpenVPN, rekeying requires a new key exchange, which can be quite expensive. Therefore, rekeying should probably be implemented with a fixed limit, in the order of a few megabytes. We can compute the encryption threshold when rekeying every 2 r blocks as 2 n-r (this figure correspond to the optimal case for an adversary, with α = β = 1/2). For example, by rekeying every megabyte, a client and server can exchange a petabyte of data before collision attacks become significant.

Exploiting Repeated Messages. We now assume that a fixed message of 2 u blocks is sent repeatedly (this will be the case for the concrete attacks we describe in Sections 4.4 and 4.5). The attacker's goal is to recover the full message, assuming that α • 2 u blocks are known or predictable.

If there is a single unknown block, we can use the previous analysis with α ≈ 1 and β = 2 -u : an attacker need roughly 2 (n+u)/2 blocks. Indeed, this should lead to roughly 2 u-1 collisions, and there is a good chance that one of these collision is between the secret block and a known block. For a more accurate analysis, we can use the results of van Oorschot and Wiener [START_REF] Van Oorschot | Parallel collision search with cryptanalytic applications[END_REF], which gives an expected complexity of π /2 • 2 (n+u-1)/2 blocks to find 2 u-1 collisions.

If there are a few unknown blocks (k = (1 -α) • 2 u ), the number of encrypted blocks required to recover them can be approximated as:

√ H k • π /2 • 2 (n+u-1)/2 ,
because the number of collision required follows the harmonic numbers 1 H k = k i=1 1 /i. On the other hand, if α is small, the attacker can use collisions to derive equations between the plaintext blocks, even if both blocks are unknown. Each collision reveals the xor between two plaintext blocks, which can seen as an edge in a graph whose vertexes are the plaintext blocks. If we model the graph as a random graph with 2 u vertexes, we know that with high probability, the graph will be fully connected when there are more than Θ(u/2 • 2 u ) edges [START_REF] Erdos | On the evolution of random graphs[END_REF]. At this point, all plaintext blocks can be recovered from a single known block. Therefore, the expected attack complexity becomes:

√ u • π /2 • 2 (n+u-1)/2
Summary of Attack Scenario. With a fixed message of size 2 u repeatedly encrypted, an attacker that knows a fraction α of the message can recover the k missing blocks of plaintext (k = (1 -α) • 2 u ) by observing about log(k) • 2 u-1 collisions. This gives an attack with a data complexity of

O log(k) • 2 (n+u-1)/2
encrypted blocks. With rekeying every 2 r blocks (r < n/2), the complexity becomes: In particular, we will apply this attack to break the security of encrypted HTTP connections when an authentication token is send with every request. We use the Beastly attacker of Figure 1 to generate a large number of requests, where the headers are mostly predictable or even controlled by the attacker (α ≈ 1), who can then recover the authentication token by observing collisions in the encrypted traffic.

O log(k) • 2 u+n+2-r .

64-BIT BLOCK CIPHER USAGE ON THE INTERNET

Many of the most influential Internet security protocols, such as TLS, SSH, and IPsec were standardized at a time when 64-bit block ciphers, such as 3DES and Blowfish, were still considered strong. Consequently, these ciphers are still widely supported on the Internet. In this section, we investigate the real-world usage of these ciphers in order to quantify the feasibility and practical impact of our attacks.

Block Ciphers in Internet Standards

Table 1 summarizes the support for various block ciphers in several versions of the TLS, SSH, and IPsec standards. The table shows that protocols that were standardized before 2000 typically supported only 64-bit ciphers (primarily 3DES), although later protocol extensions enabled 128-bit ciphers (primarily AES). Still, old versions of these protocols remain quite popular on the web. Notably, each standard specifies a mandatory cipher that "MUST" be supported for interoperability, and in most of these specifications, the mandatory encryption algorithm is 3DES. This means that all implementations of TLS, SSH, and IPsec must implement 3DES, and unless the user explicitly disables it, they will offer to negotiate 3DES with their peers.

For example, in TLS 1.0 and 1.1, 3DES is the mandatory encryption algorithm, so all TLS libraries implement it and a vast majority of web servers support it. Although TLS 1.2 changed the mandatory cipher to AES, it still explicitly recommends 3DES as secure [13, Sec. 7.3]:

If you negotiate 3DES with a 1024-bit RSA key exchange with a host whose certificate you have verified, you can expect to be that secure.

As a result, mainstream TLS libraries still treat 3DES to be at the same security level as AES-128. For example, until we disclosed the attacks in this paper, OpenSSL included 3DES ciphersuites in its HIGH-security list (it has now been moved to MEDIUM). Moreover, while the use of RC4 in TLS has been explicitly deprecated in RFC7465 in response to recent attacks, 3DES continues to be trusted by TLS libraries.

In fact, it has even started being recommended as the new backup cipher in place of RC4.2 TLS does not mandate rekeying for short block ciphers, and so TLS libraries leave the decision to rekey to their applications.

In SSH version 1, the strongest available ciphers are all 64bit block ciphers: 3DES, Blowfish, and IDEA, and although SSH 2 introduced AES-based ciphers, it still labeled 3DES as the mandatory cipher. Consequently, popular implementations such as OpenSSH still use 3DES as the default cipher for SSH-1 connections, and 3DES continues to be the most widely supports cipher in SSH. 3 SSH standards recommend that implementations rekey after every 1GB of data, or after every 2 n/4 blocks [START_REF] Bellare | The Secure Shell (SSH) Transport Layer Encryption Modes[END_REF], but many popular SSH clients do not implement this feature.

The early IPSec specifications also widely used and recommended 3DES. For example, RFC4835 recommended 3DES as a mandatory (MUST) algorithm until 2007, although the more recent RFC7321 has downgraded it to a "MAY". Consequently, most IPSec libraries continue to support 3DES, and since IPSec deployments tend to be stable over a long period of time within corporate networks, we anticipate that the algorithm may continue to be supported on IPSec networks for the foreseeable future.

In summary, short block ciphers and 3DES in particular have widespread support in major secure transport protocols, making them vulnerable to the attacks described in this paper. However, to evaluate the real-world impact of this vulnerability, the key question is whether these ciphers are actually used in connections between popular clients and servers. In the rest of this section, we attempt to quantify this usage.

3DES and Blowfish usage in VPNs

TLS, SSH, and IPSec are often used to implement tunnels or virtual private networks (VPNs) across untrusted network connections. We have already discussed the widespread support for 64-bit block ciphers in these protocols, but estimating whether these ciphers are actually negotiated in practice is hard, because unlike web servers, most VPN services are not publicly accessible, and each VPN server may use its own configuration. However, we found a few VPN solutions that use 64-bit ciphers by default.

IPsec. Most IPSec-based VPN clients support 3DES for interoperability. Notably, some versions of Microsoft's L2TP VPN client use 3DES by default 4 ; some versions of MAC OS X negotiate 3DES with certain VPN servers5 ; and some versions of CISCO IPsec VPN devices implement hardware optimizations for 3DES and consequently prefer it over other ciphers. 6OpenVPN. OpenVPN is a popular open-source VPN solution originally written by James Yonan. The default encryption for the transport protocol of OpenVPN is Blowfish, a 64-bit cipher, in CBC mode. OpenVPN supports two different ways of generating session keys to encrypt the messages. In pre-shared-key mode, static keys are used for all the traf- fic. In particular, there is no limit to the lifetime of those keys. In TLS mode, session keys are generated with a TLS handshake, using certificates to authenticate the peers. The session keys are updated periodically, with limits on the number of packets, the number of bytes, or a session time.

The default configuration rekeys the tunnel every hour. In addition, the tunnel is rekeyed shortly before 2 32 packets in TLS mode, because the packet counter is a 32-bit integer. In pre-shared-key mode, the packet counter is a 64-bit integer.

3DES usage in HTTPS

3DES is the second most widely supported cipher (after AES) in HTTPS servers, with about 87% of servers supporting it. 7 Furthermore, all popular web browsers support 3DES. The cipher that is actually negotiated for a TLS connection is chosen by the server, based on its local preference order and on the order in which the client advertises its ciphersuites. Since most modern browsers and servers prefer AES over 3DES, we find evidence that 1-2% of all TLS connections likely use 3DES in CBC mode, as detailed below.

Browser Telemetry. Telemetry data from Mozilla Firefox (given in Table 2) show that 3DES is used for more than 1% of HTTPS connections from Firefox browsers. Interestingly, the use of 3DES with Firefox has actually increased recently, as a consequence of the removal of RC4 from the list of supported ciphers in version 36 (following [START_REF] Alfardan | On the Security of RC4 in TLS[END_REF] and RFC 7465). Indeed a number of servers are configured to use, in order of preference, first RC4, then 3DES, and now use 3DES with Firefox.

Other browser vendors have privately reported the following telemetry data to us. Microsoft sees 1.2% 3DES connections for Internet Explorer and Edge, but only 0.8% system wide (the lower value can be explained by the fact that some applications still support RC4). Google Chrome sees 1.1% of connections using 3DES, but this number peaked at 1.6% soon after RC4 was disabled. If a web server runs on IIS 6.0 (i.e. Windows XP or Windows Server 2003), it will offer only RC4 and 3DES ciphersuites, unless support for AES ciphersuites has been added. If a modern web browser visits the website over HTTPS, the connection will use 3DES. According to web server surveys9 , IIS 6.0 powers about 1.9% of SSL enabled web servers, but it is likely used even more within corporate networks, and these servers would not appear in public scans.

Long-lived HTTPS connections. In order to mount the attack in practice, we need to find client and servers that not only negotiate the use of 3DES, but also exchange a large number of HTTP request in the same TLS connection (without rekeying). This is possible using a persistent HTTP connection, as defined in HTTP/1.1 (Keep-Alive).

On the client side, all browsers that we tested (Firefox, Chrome, Opera) will reuse a TLS connection as long as the server keeps it open. On the server side, we found that a number of HTTP servers will close the TLS connection even when it is still active. In particular, Apache and Nginx limit the number of requests sent in the same connection, with a maximum of 100 in the default configuration 10 the other hand, IIS does not seem to have such a limit. In practice, many high profile servers accept a very large number of requests in a single TLS connection. We made some experiments using a simple Perl script to send simple HTTP requests over a TLS connection, using pipelining to maximize the throughput. As seen in Table 4, we found that about half of the servers in Alexa's top 10 support a large number of requests without rekeying. For a better estimate of the number of vulnerable servers, we tested servers from Alexa's top 10k that negotiate 3DES with a modern client. We identified 11483 different HTTPS servers 11 , and found that 226 of them (1.9%) negotiate 3DES with a modern client. Moreover, 72 of these (0.6% of the total) also accept to keep a connection open for at least 800k requests. Consequently, the duration of the attack is not unrealistic, at least from the viewpoint of browsers and servers, and we estimate that at least 0.6% of HTTPS connections are vulnerable to our attacks. Downgrading to 3DES. From our measurements, only 1-2% of HTTPS connections use 3DES, and perhaps even fewer of these connections are to servers that allow longlived TLS connections. However, ignoring the danger posed by 3DES would be dangerous for several reasons. 3DES is typically the second or third most preferred encryption algorithms in HTTPS, so any change in the client or server configurations, say in response to some future attack on AES, would cause a large number of connections to fallback to 3DES. Furthermore, as recent downgrade attacks on TLS (e.g. FREAK) have demonstrated, protocol and implementation flaws can sometimes cause a weaker cipher to be negotiated. For example, if a downgrade attack from TLS 1.2 to SSL 3 becomes possible, then the strongest SSL 3 cipher that can be negotiated may well be 3DES. As an example, we describe a downgrade attack to 3DES that is currently possible on TLS connections. Although it does not enable our full attack, it nevertheless serves as a useful warning for practitioners. [START_REF] Langley | Transport Layer Security (TLS) False Start[END_REF] is an optimization to the TLS handshake that reduces its latency. A client implementing False Start will start sending data before receiving the Finished message from the server. This allows an attacker to force the selection of a ciphersuite by tampering with the ServerHello message (he can replace AES by 3DES, for example) and the client will start sending data before verifying that the ciphersuite was really selected by the authentic server. If the client is willing to send millions of requests and gigabytes of data before finishing the handshake, this could allow our attack even against a server that would not select a 3DES ciphersuite. While 3DES ciphersuite are not recommended for use with False Start in the RFC draft [START_REF] Langley | Transport Layer Security (TLS) False Start[END_REF], it turns out that they are white-listed for use with False Start with Internet Explorer. We have informed the Microsoft security team and they decided to remove 3DES from this white-list.

Downgrading False Start. TLS False Start

ATTACKING AUTHENTICATED HTTP OVER TLS AND OPENVPN

We now demonstrate concrete attacks against authenticated HTTP sessions even when they are secured by TLS or OpenVPN. First, we identify a few examples of secret authentication credentials that are repeatedly sent by the browser on every request. We then show how we can recover these secrets using block cipher collisions.

HTTP bearer tokens

Cookie-based Sessions. Modern HTTPS websites use a variety of methods to manage authenticated sessions with their clients. The most popular mechanism is secure cookies as specified in RFC6265. Once a user has logged in, the server sets a cookie containing a secret value on the user's browser. The browser will then send the cookie on all subsequent requests to the website, implicitly authenticating the user. For example, if domain.com sets a cookie C=XXXX, a subsequent HTTPS request from the browser looks like: GET /path/to/file HTTP/1.1 User-Agent: Mozilla/4.0 ... Host: domain.com Cookie: C=XXXXX Accept-Language: en-us Accept-Encoding: gzip, deflate Connection: Keep-Alive Cookies are sensitive, because an attacker who obtains a session cookie can then log in as the user from a different browser. The cookie acts as a bearer token that carries the user's delegated credential. Except for its short-lived nature, it has the same security requirements as a password. Indeed, many websites, such as Facebook, use cookies with very long expiry times, making cookie theft even more attractive.

A cookie for a website is normally included in all requests to that website whether that request was initiated by the user, or a script on the website, or even by a different website. Browsers sometimes impose stricter rules for this last category of requests, called cross-origin or cross-domain requests. For example, XmlHttpRequests sent from one domain to another may not have cookies attached. However, cross-domain requests for images or iframes will still send cookies. HTTP BasicAuth. On corporate networks and even on the web, many websites are protected using the HTTP Basic Authentication mechanism specified in RFC7617. When the server asks for Basic authentication, the browser prompts the user to enter a username and password into a special dialog and then sends this information (in plaintext) as an HTTP header of the form:

Authorization: Basic dGVzdDoxMjPCow=
Once a user has entered his login information once, the browser will typically cache this information and use it on all subsequent requests to the server. Notably, even if a different website creates a cross-domain request to the authenticated server, the BasicAuth credentials will be automatically sent by the browser.

BasicAuth credentials contain the user's password and are hence security-critical. One should only use this authentication mechanism over HTTPS but a number of corporate websites use BasicAuth over HTTP, under the assumption that their users can only access the website over a VPN or some other secure connection.

OAuth and OpenID Connect Access Tokens. With the growth in popularity of single sign-on protocols, many websites now allow users to login with third-party credentials, such as OAuth or OpenID Connect tokens, issued by major websites like Google and Facebook. These tokens are effectively bearer tokens that must then be attached to all authentication and authorization requests and are sent either within the URI or in an Authorization header. While the use of these tokens is specific to each website, an attacker can usually repeatedly trigger the sending of these tokens by re-initiating the login sequence. An attacker who steals one of these tokens can then impersonate the user as well as retrieve sensitive data about the user from the login provider.

The Beastly Attack Scenario

Our attack scenario, depicted in Figure 1, is similar to the setup used in recent attacks on RC4 [START_REF] Alfardan | On the Security of RC4 in TLS[END_REF][START_REF] Garman | Attacks Only Get Better: Password Recovery Attacks Against RC4 in TLS[END_REF][START_REF] Vanhoef | All Your Biases Belong to Us: Breaking RC4 in WPA-TKIP and TLS[END_REF]. The attacker wants to steal some bearer token that is being repeatedly sent by a browser to a website secured with HTTPS, or an HTTP website accessed through a VPN. We assume that the attacker can control some JavaScript on a web page loaded by the user's browser, either by actively tampering with an HTTP response on the wire, or by hosting a malicious website that the user is fooled into visiting. We also assume that the attacker can observe all the encrypted traffic between the target browser and the secure website.

We further assume that the data is encrypted with a 64-bit block cipher in CBC mode (either an HTTPS connection where the client and server have negotiated 3DES, or an HTTP connection though a VPN encrypted with Blowfish or 3DES). Suppose the victim is already logged in to a website and has a session cookie. The attacker runs malicious JavaScript code on the victim's browser that repeatedly sends HTTP queries to the target website server, each containing the session cookie. If he sends close to 2 32 queries, a collision is expected between a ciphertext block corresponding to the cookie (ci), and a known block (cj), containing a known part of the query. The collision attack against CBC reveals the session cookie: pi = pj ⊕ ci-1 ⊕ cj-1.

Note that most of the traffic generated by the attacker is known or predictable. The requested URL is chosen by the attacker, and all the headers excepted the cookie are predictable and can be observed in any plaintext HTTP traffic. We will assume that the Cookie takes 16-bytes, i.e. two blocks, and that the attacker has aligned the cookie to a block boundary using other headers. As explained in Section 2.2, if a query contains 2 u known blocks, the number of encrypted blocks required for the attack is about:

√ H2 • π/2 • 2 (n+u-1)/2 .
In practice, an HTTP query is about 512 bytes (64 blocks), which implies a total complexity of 2 35.1 blocks (2 29.1 queries), and a total captured trace of size 280 GB. However, the attack can be made faster by using larger queries: this increases the total amount of data to capture, but it reduces the total number of queries. Since the speed of clients and servers is dependent on the number of queries, a larger query size can result in a faster attack overall. In our experiments, we got good results with 4 kB queries (512 blocks). In this setting, the attack requires 2 36.6 blocks (785 GB), but this corresponds to only 2 27.6 queries: increasing the requests size by a factor 8 (from 512 bytes to 4 kB) increases the total data to capture by a factor √ 8, and reduces the number of queries needed by a factor √ 8. In practice large queries can be produced by adding a long query string to the URL.

Proof-of-concept Code

The attacker code consists of two parts: a JavaScript program that sends a large number of HTTP requests, and a network adversary who processes the resulting ciphertext to recovers a 16-byte secret.

Man-in-the-browser code. We experimented with hidden <img> tags in a web-page with Javascript code to the onload event to reload the images repeatedly, and web workers issuing XmlHttpRequests. Cookies are automatically inserted when loading images from a different domain, and are also included in cross-domain XmlHttpRequests if the withCredentials property is set to true (this is only allowed for synchronous request, and the request result can not be read, but these restrictions don't prevent our attack). According to our experiments, request are generated faster using XmlHttpRequest. In order to avoid caching, we request a non-cacheable resource. Alternatively, we can include a unique query string in each URL, but the responses are still cached by the client and this can affect the query rate. We experimented with several browsers, and we obtained the best results with Firefox Developer Edition 47.0a212 .

Recovering collisions. We captured the encrypted packets with tcpdump and used a C++ program to extract the ciphertext blocks (using libpcap). In both the HTTPS attack and the OpenVPN attack, each HTTP query is sent in a separate encrypted record, which contain the plaintext at a fixed position, as well as some extra information (packet number, padding, MAC, ...). Therefore, it is easy to know to which plaintext block corresponds each ciphertext block, and to align the cookie to a block limit.

After capturing all the traffic, the C++ program sorts the ciphertext blocks in order to locate collisions. Since the amount of data is quite large (hundreds of gigabytes), we use the external sort implementation of the stxxl library. With a NAS storage, sorting the data took around four hours.

Attacking Basic Auth over OpenVPN

To demonstrate the attack against OpenVPN, we use a preshared-key tunnel between two physical machines running Linux, with Firefox Developer Edition 47.0a2 on one side, and an nginx server on the other side. Access to the server is protected by BasicAuth, and the user has entered his credentials. Using the default OpenVPN settings, the tunnel is encrypted with Blowfish in CBC mode.

We use the Javascript code described in the previous section to send a large number of requests to the server though the tunnel. We found that increasing the size of the request to 4 kB does not significantly reduce the query rate, but reduces the number of queries required for the attack. In our setting, the browser generates about 2900 requests per second, using several web Worker running in parallel. We expect the first collision after roughly 2 32.3 blocks (40 GB), i.e. one hour. In practice, we detected the first collision early, after only 30 minutes (2 31.3 blocks); as expected, the predicted xor difference was correct. The full attack needs about 2 36.6 blocks (785 GB) to recover a two-block secret out of 4 kB messages; this should take about 19 hours in this setting. In our demo, it took 18.6 hours and 705 GB, and we successfully recovered the 16-byte authentication token.

OpenVPN in TLS mode. In TLS mode, OpenVPN rekeys the tunnel every hour with the default settings (as apposed to the pre-shared-key mode used above that doesn't do any rekeying). With our experimental setting, this means we can only capture about 2 23.3 requests encrypted with a given key, i.e. 2 32.3 blocks. Therefore, we expect to detect a collision with probability close13 to 1/2. In order to recover a two-byte secret out of 4 kB messages, we need about 384 collisions as explained in Section 2.2. Therefore, this attack will take roughly 768 hours, or 32 days.

This illustrate the point that keys should be changed well before reaching 2 32 blocks: if each session is broken after 2 32 blocks, there is still a collision with probability roughly 1-e -1/2 ≈ 0.4. This increases the time required by the attack to 40 days, but it will still succeed with high probability.

Attacking Secure Cookies over HTTPS

The attack against HTTPS connection is very similar to the attack against OpenVPN, as long as we have a client and server that negotiate 3DES, and that keep a connection open for a long time.

Vulnerable Websites. As detailed in Section 3.3, about 0.6% of the top Alexa 100K websites support 3DES and allow long-lived HTTPS connections. This list contains many high-profile e-commerce and banking websites, including the ones shown in Table 5. In addition, we found a number of domains were the server serving domain.com will use 3DES, but it just redirects the client to a better configured server for www.domain.com. This could still open the way for our attacks, if sessioncookies for www.domain.com are set at the top-level domain and hence also sent to domain.tld. The last three websites in Table 5 belong to this category.

Proof-of-Concept Attack Demo. In our setup we use Firefox Developer Edition 47.0a2 running on Linux and an IIS 6.0 server in a Windows Server 2003 R2 SP2 Virtual machine. The default configuration of IIS 6.0 with all recommended updates offers only RC4 and 3DES ciphers, and will use 3DES with Firefox and other recent browsers where RC4 is disabled. Moreover, IIS 6.0 supports HTTP/1.1 and keeps an active connection open for an arbitrary long time.

We use the Javascript code described in Section 4.3, but we note that with several Workers running in parallel (or several <img> tags), modern browsers open a few parallel connec-Corporate Table 5: High-value websites that negotiate 3DES with modern browsers, and accept at least 1 million requests in the same TLS session tions to the server (typically, 6) and split the requests over these connections. For our attack, we need to maximize the throughput over a single connection. This can be achieved by disturbing some of the connections so that most of request are send in a single. In our setup, we used iptables rules to limit the rate of all connections except one. In a real attack, this would be done by an active man-in-the-middle, but a passive man-in-the-middle can also mount the attack -it will just take more time to collect the data.

On Firefox Developer Edition 47.0a2, with a few dozen Workers running in parallel, we can send up to 2000 requests per second in a single TLS connection. To further reduce the time needed for the attack, we inject a padding cookie to expand the requests to 4 KB (512 blocks). In our setting this reduces the rate to 1500 requests per second, but it still leads to a faster attack. Again, we expect the first collision after roughly 2 32.3 blocks (40 GB), i.e. 2 23.3 queries. This should take slightly less than two hours.

In our experiment, we were lucky to detect the first collision after only 25 minutes (2 20.1 requests), and we verified that the collision revealed the xor of two plaintexts blocks. As seen previously, the full attack should require 2 36.6 blocks (785 GB) to recover a two-block cookie, which should take 38 hours in our setting. Experimentally, we recovered the two-block cookie after only 30.5 hours and 610 GB.

Note that special care must be taken to recover the first block of a TLS fragment. When a collision involves the first ciphertext block (c

(j) i = c (j ) 0 ), this gives an equation involving the IV (c (j) i-1 = c (j ) -1
). In particular, this requires special treatment for TLS 1.0, because the IV of a given of a given record is not explicitly included in the message: it is the last ciphertext block of the previous record.

Our attack above relied on knowing most of the plaintext, but if we have enough data we can even recover most of the plaintext using just a single known block. In our experiment, after 65 hours (2 28.3 requests, 1.3TB) we can recover 492 blocks out of 510, assuming a single known plaintext block.

IMPACT AND MITIGATION

We have demonstrated the first concrete attacks on mainstream Internet protocols that exploit block cipher collisions. Our attacks can recover valuable secrets such as HTTP cookies and passwords in under 40 hours. Our attacks impact a majority of OpenVPN connections and an estimated 0.6% of HTTPS connections to popular websites. We expect that our attacks also impact a number of SSH and IPsec connections, but we do not have concrete measurements for these protocols. Like many recent attacks on TLS, such a BEAST and RC4 NOMORE, the underlying principles behind our attacks were well known to cryptographers. Our goal is to raise awareness among practitioners about the vulnerabilities of short block ciphers and on safe ways of using them.

Comparison with RC4 attacks

Our attack scenario is very similar to the setup of the recent attacks on the use of RC4 in HTTPS. We use the same man-in-the-browser setting to generate a large number of HTTP requests, and the data complexity of our attacks is comparable to these prior works:

• the first attack by Al Fardan et al. [START_REF] Alfardan | On the Security of RC4 in TLS[END_REF] uses between 2 28 and 2 32 sessions, with rekeying for each session, to recover the first 220 bytes a the message (but the cookie is not usually in these 220 bytes);

• the second attack by Al Fardan et al. [START_REF] Alfardan | On the Security of RC4 in TLS[END_REF] uses between 2 33 and 2 34 request, in the same TLS session or in different sessions, to recover a cookie;

• Garman et al. [START_REF] Garman | Attacks Only Get Better: Password Recovery Attacks Against RC4 in TLS[END_REF] improved the first attack to require only 2 26 sessions when targeting a BasicAuth password, using a better guessing strategy;

• the latest attack by Vanhoef and Piessens [START_REF] Vanhoef | All Your Biases Belong to Us: Breaking RC4 in WPA-TKIP and TLS[END_REF] requires 2 30.2 requests, in the same TLS session or in different sessions, to recover a cookie.

In comparison, our attack requires only 2 29.1 short queries of 512 bytes (280 GB in total), which can be reduced to 2 27.6 longer queries of 4 kB (785 GB in total). However, these numbers are for the case when all the data is encrypted within the same session. Even if the amount of data sent on a single connection is limited, as long as the limit is close enough to the birthday bound, we can still mount our attacks across multiple parallel and sequential sessions, albeit with a higher data and time complexity.

Mitigation

The obvious way to avoid these attacks is to stop using legacy 64-bit block-ciphers. There is no good reason to configure a VPN or an HTTPS server to prefer 3DES (or Blowfish) over AES. AES is more secure, is a FIPS standard, and will almost certainly be faster: it is implemented in hardware in most server and desktop CPUs, and can be implemented efficiently in dedicated hardware when an extremely high throughput is required.

On the other hand, there are specific uses of cryptography were 128-bit block ciphers can not be used, because of legacy reasons, or due to the relatively large hardware footprint of 128-bit ciphers (in this case, lightweight 64-bit block ciphers such as PRESENT or HIGHT would typically be used). In these scenarios, protocol designers should pay close attention to the issue of birthday attacks. In particular, they should verify that the amount of data encrypted with a fixed key is significantly smaller than 2 32 blocks, or use modes that provide security beyond the birthday bound, such as CENC [START_REF] Iwata | New blockcipher modes of operation with beyond the birthday bound security[END_REF] or PMAC plus [START_REF] Yasuda | A new variant of PMAC: Beyond the birthday bound[END_REF].

Concretely, we recommend the following measures to prevent our attack:

1. Web servers and VPNs should be configured to prefer 128-bit ciphers. According to our scans, about 1.1% of the top 100k web server from Alexa, and 0.5% of the top 1 million, support AES but prefer to use 3DES.

2. Web browsers should offer 3DES as a fallback-only cipher, to avoid using it with servers that support AES but prefer 3DES.

3. TLS libraries and web browsers and servers should limit the length of TLS sessions with a 64-bit cipher. This could be done in TLS renegotiation, or in some cases by closing the connection and starting a new one (i.e. limiting HTTP/1.1 Keep-Alive, SPDY, and HTTP/2 with 3DES ciphersuites).

Responsible Disclosure

We have communicated our results and concerns to the OpenVPN team, and to various website owners, browser vendors, and TLS libraries. They all acknowledged the issue, and are working on implementing countermeasures. The TLS vulnerability received CVE number CVE-2016-2183. OpenVPN will display a warning to users who choose to use 64-bit ciphers and encourage them to transition to AES-GCM (cipher negotiation is also being implemented in the 2.4 branch). It will also implement a default renegotiation limit of 64MB when used in TLS mode. OpenSSL has moved 3DES ciphersuites from the HIGH category to MEDIUM in the 1.0.2 branch, and will disable it by default in the upcoming 1.1.0 release. Akamai will offer an option for web server administrators to drop 3DES from the offered ciphers. Apple has disabled 3DES on icloud.com and is recommending that all its customers disable 3DES on their websites.

Currently, most browsers see about 1% of their connections using 3DES, and vendors consider this number too high to simply disable 3DES on the client side, since too many websites would be broken. So, they are instead considering implementing data limits per connection to force rekeying, or offering 3DES ciphersuites only in a fallback negotiation if no AES ciphersuite is acceptable to the server. Mozilla is implementing data limits for all ciphersuites: https://bugzilla.mozilla.org/show bug.cgi?id=1268745 . Microsoft has removed 3DES from the False Start whitelist: https://technet.microsoft.com/library/security/3155527.aspx More details about implemented countermeasures will be added to our webpage as they become available: http://sweet32.info

Figure 2 :

 2 Figure 2: CBC mode

Table 1 :

 1 Block ciphers in popular versions of Internet protocols; 64-bit ciphers are shown in red

	Protocol Year	Block ciphers	Mandatory Rekey
	TLS 1.0 1999	3DES, DES, IDEA	3DES	-
	TLS 1.1 2006	AES, 3DES, DES	3DES	2 78
	TLS 1.2 2008	AES, 3DES	AES	2 78
	SSH 1	1995	3DES, DES, IDEA	3DES	-
	SSH 2	2006 AES, 3DES, Blowfish	3DES	2 30 ,
	IKEv1 1998 3DES, DES, Blowfish	DES	-
	IKEv2 2010 AES, 3DES, Blowfish	3DES	-
	IPsec	2014	AES, 3DES	AES	1GB

1

Assuming that the time to recover each block follows a geometric law

Table 3 .

 3 Windows XP Clients and Windows 2003 Servers. The Windows XP and Windows Server 2003 operating systems do not support AES-based ciphersuites, although support for AES can be added with an optional hotfix. With the default configuration, they support only RC4, 3DES, DES, and RC2-40. While these operating systems are not supported anymore by Microsoft, they still have users, and this creates situations where the best available cipher is 3DES. If a client uses Internet Explorer on Windows XP or Windows Server 2003 to connect to a modern web server (with no RC4 ciphersuites), the connection will use 3DES or fail. Indeed, supporting Windows XP clients is the main stated reason for servers to continue supporting RC4 and 3DES.

	7 https://securitypitfalls.wordpress.com/2016/04/17/
	february-2016-scan-results-incomplete/

Table 4 :

 4 . On Maximum connection lifetime for Alexa's top 10 servers (detected experimentally). The " †" symbol marks servers which accept at least one million requests in a single TLS connection.

	Website	connection closed after
	google.com	1 hour †
	facebook.com no limit detected †
	youtube.com	no limit detected †
	yahoo.com	no limit detected †
	live.com	up to one day †
	baidu.com	100 requests
	amazon.com	100 requests
	wikipedia.org 100 requests
	qq.com	2000 requests
	twitter.com	50 requests

https://wiki.mozilla.org/Security/Server Side TLS

https://blog.binaryedge.io/2015/11/10/ssh/

https://support.microsoft.com/en-us/kb/325158

http://www.jacco2.dds.nl/networking/openswanmacosx.html

[START_REF] Bellare | A concrete security treatment of symmetric encryption[END_REF] http://www.cisco.com/c/en/us/td/docs/ios/12 2/12 2z/ 12 2zj/feature/guide/gtaimvpn.html

https://github.com/jvehent/cipherscan

http://www.securityspace.com/s survey/sdata/201604/ servers.html

The setting is called MaxKeepAliveRequests for Apache, and keepalive_requests for Nginx.

We tested common sub-domains: www, m, secure, signin, auth, account, login

We have similar results with the stable version Firefox 48.0 which was released after we made our experiments.

The probability can be computed as 1 -e -2 32.2 2 32.2 /2 64 .

Acknowledgement K. Bhargavan received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 683032 -CIRCUS).


domain: math shs

text:
Clara Benedicto

Angel Gutiérrez

Adela Jaime

When the theoretical model does not fit our data: A process of adaptation of the Cognitive Demand model

Keywords: Theoretical framework, adaptation, cognitive demand, mathematical problem solving

Some theoretical models emerged from specific mathematical contents or educational levels, so they are well adapted to the context where they were created but, sometimes, they do not fit well in a different context. Related to the issue of the need to go beyond a specific theory when researching a phenomenon, to solve the tension between home-grown needs and borrowed theories, we present the reasons for and steps of an adaptation we have had to do of the Cognitive Demand model so that it fits the requirements of our research questions, methods and data. We systematized the definition of the model stated by its authors, and completed this definition with some necessary statements. Then, we re-stated some characteristics of the model to avoid inconsistencies when using it. Finally, we particularized the general model to several specific mathematical topics.

Introduction

The choice of a specific theoretical framework is a key decision for researchers when they start working on a new research project. However, sometimes, researchers wish to use a theoretical model in a context that the model does not fit well, and they decide to modify the theoretical model to adapt it to the new requirements. We present our experience of fitting a theoretical model with flexibility so it can be adapted to contexts and used in ways the model had never been used.

We are developing a research project1 aimed to better understand the cognitive processes of primary and lower secondary mathematically talented students (i.e., students showing mathematical abilities clearly over average students) when solving problems. A characteristic of those students is that they demand problems making them engage in high level of reasoning. A way for teachers to succeed in it is by posing them that kind of problems. Then, we had to find a way to determine the cognitive effort required by problems and done by students when solving them. The Cognitive Demand model (Smith & Stein, 1998) fitted our requirements, so we integrated it in our theoretical and methodological research frameworks. However, when we used this model to analyze our data, we found some difficulties in applying it due to ambiguity or inconsistency of results, so we decided to adapt it to our needs. We detail in next pages the steps in the process of adaptation, the reason for each step, and the resulting theoretical model. We present a reconstruction of the main parts of the real recurrent process, which has taken several years and still has not been finished.

The next section presents the characterization of the Cognitive Demand model as stated by its authors. Third to sixth sections present examples of the difficulties we found and the steps we followed to adapt the original model: organizing the original characterization, completing such charac-terization with some new statements, re-wording some characteristics of the model to avoid inconsistencies when using it, and particularizing the new general characterization of the model to different specific mathematical topics. Due to space limitations we cannot show the details for all levels of cognitive demand, but only an example of each step for certain levels.

The starting point: The levels of Cognitive Demand

The Cognitive Demand model resulted after a process of characterization of mathematical tasks according to their "potential to engage students in high-level thinking" (Smith & Stein, 1998, p. 344). It includes four levels of cognitive demand that assess the cognitive effort required from students to solve a mathematical task. These levels are labelled (Smith & Stein, 1998) as memorization, procedures without connections to concepts or meaning, procedures with connections to concepts and meaning, and doing mathematics, when complex mathematical thinking is required. Each level is defined by a set of characteristics paying attention to different aspects of the solutions of problems. We present in Table 1 the characteristics of two levels that are the ground for the rest of the paper.

Procedures without connections 2.1. Are algorithmic. Use of the procedure either is specifically called for or is evident from prior instruction, experience, or placement of the task. 2.2. Require limited cognitive demand for successful completion. Little ambiguity exists about what needs to be done and how to do it. 2.3. Have no connection to the concepts or meaning that underlie the procedure being used. 2.4. Are focused on producing correct answers instead of on developing mathematical understanding. 2.5. Require no explanations or explanations that focus solely on describing the procedure that was used.

Procedures with connections 3.1. Focus students' attention on the use of procedures for the purpose of developing deeper levels of understanding of mathematical concepts and ideas. 3.2. Suggest explicitly or implicitly pathways to follow that are broad general procedures that have close connections to underlying conceptual ideas as opposed to narrow algorithms that are opaque with respect to underlying concepts. 3.3. Usually are represented in multiple ways, such as visual diagrams, manipulatives, symbols, and problem situations. Making connections among multiple representations helps develop meaning. 3.4. Require some degree of cognitive effort. Although general procedures may be followed, they cannot be followed mindlessly. Students need to engage with conceptual ideas that underlie the procedures to complete the task successfully and that develop understanding. To attain our research objectives, we created rich problems intended to be posed to whole-class groups, consisting of several related questions of increasing complexity, in such a way that all students should be able to solve the first questions but only the more able students could solve all of them. The levels of cognitive demand allow us to classify the questions in a problem and decide whether each question is more appropriate for average students or for talented students.

The Cognitive Demand model was created after the analysis of problems that, most of them, were in the quite algorithmic areas of school arithmetic and algebra (Stein & Smith, 1998;[START_REF] Stein | Implementing Standardsbased mathematics instruction[END_REF], but we are trying to use the model to analyze problems in mathematical topics very different from the previous ones, as are plane geometry, geometric patterns (pre-algebra) and visualization.

Identifying inconsistencies between the characteristics of the levels

After using the model to analyze different problems, a difficulty related to lack of consistency between some levels arose. We exemplify it by analyzing a problem consisting of several questions guiding students to discover and prove a formula to provide the number of diagonals of any polygon. The problem has two parts: the first one can be seen in Figure 1; the second part asks students to draw and count all the diagonals of the same polygons and to fill in a table, to calculate the number of diagonals of a 20-sided polygon, to generalize the procedure of calculation of the diagonals to any given polygon, and to prove this relationship. We present our analysis of question 1a (Figure 1) by considering typical average students' solutions that do not go further than what is asked to do. Regarding the level of procedures without connections, question 1a is algorithmic and the statement suggests the procedure to be used, namely to draw the diagonals from a given vertex and count them to fill in the table, so it fits characteristic 2.1 in Table 1. The polygons drawn in the statement guide students to draw the diagonals from a specific vertex, so there is little ambiguity about what they have to do and how to do it (it fits 2.2), and it does not require explanations (it fits 2.5). On the other hand, the procedure to be used has connections with the relationship between the number of sides and diagonals from a vertex of polygons (it does not fit 2.3), although question 1a is focused on producing correct answers, not on developing understanding of that relationship (it fits 2.4).

Regarding the level of procedures with connections, question 1a does not fit 3.1, since it is not focused to make students develop understanding of the underlying relationship. However, it fits 3.3,

since, to answer it, students use geometric and numeric representations of information about polygons and diagonals: the numeric representation shows the general relationship between number of sides and diagonals, while the geometric representation may help students understand why it is true.

So the question has the potential to let students connect both representations, which would help them develop the meaning for the relationship. Question 1a fits 3.2, since it explicitly suggests a procedure that is closely connected to the underlying concepts, the number of sides and diagonals from a vertex of polygons. Question 1a does not fit 3.4 since its procedure may be followed without need of being mindful, and a correct solution to it does not require understanding the underlying relationship between number of sides and diagonals from a vertex of polygons.

The epistemological conception of the levels of cognitive demand is that they are mutually exclusive. We see that question 1a fits several characteristics of each level procedures without connections and procedures with connections, so it is unclear to which level of cognitive demand should it be assigned. This happens because some characteristics of these levels, as stated in Table 1, are not precise enough, which can lead to errors when trying to assign a level of cognitive demand to some problems. The most evident vagueness, or contradiction, happens with characteristics 2.1 and 3.2.

Organizing the characteristics of the levels and filling their gaps

After having identified the difficulty analysed above, we made a detailed comparison of the characteristics of each pair of consecutive levels, to identify possible weaknesses and modify their wording to correct them. We noted that the characteristics of levels (see examples in Table 1) focused on six domains of objectives of a problem or its process of solution. These six domains of characteristics are: Procedure of solution, objective of the problem, required student's cognitive effort, mathematical contents implicit in the problem, kind of explanations required, and types of representations used in the solution. The domains helped us arrange the characteristics of the levels of cognitive demand provided by [START_REF] Smith | Selecting and creating mathematical tasks: from research to practice[END_REF] and identify some gaps in the definitions of the levels. Table 2 shows the assignation of the characteristics of the levels to the domains. It also shows that two domains are considered only in the definitions of a level, and that 3.4 includes references to two domains, while several characteristics of the level doing mathematics refer to a same domain.

Levels of cogn. demand

Next step to improve the usability of the original definition of the Cognitive Demand model was to complete the definitions of the levels, by including characteristics referring to the missed domains, taking care that each new characteristic is consistent with the corresponding characteristics of the other levels. Table 3 shows the new characteristics, to be added to those in Table 1 to make a more complete description of the levels of cognitive demand.

Procedures without connections 2.6 (representations). One or more representations may be used (arithmetical, geometrical, visual diagrams, manipulatives, etc.). When several representations are used, students use them independently, i.e., without establishing connections neither between them nor with the underlying concepts and ideas.

Procedures with connections 3.5 (explanations). Require explanations that focus on the underlying relationships by using specific examples.

Table 3: Characteristics added to the levels of procedures without and with connections

Having completed the definitions of the levels by merging Table 1 and Table 3, we were ready to refine the characteristics that induced wrong or multiple identifications of the cognitive demand in some problems, like the problem analysed above (number of diagonals of polygons).

Refining the characteristics of each level

A necessary feature of any set of disjoint categories is that their definitions have to make it clear the border between adjacent categories. As we showed above, this is not the case for the levels of cognitive demand. To refine the definitions of the levels, we made a systematic comparison of the characteristics in the same domain and decided to do some changes in their wording to make them more explicit and to clearly raise the particularities of each level.

The key difference between the levels of procedures without connections and procedures with connections is that, in the lower level, students do not need to be aware of the mathematical relationships implicit in the problem to solve it correctly but, in the higher level, students need to use consciously such relationships to solve correctly the problem. Table 4 shows the result of the comparison between those levels, where we have italicised the new characteristics (see Table 3) and the characteristics in [START_REF] Smith | Selecting and creating mathematical tasks: from research to practice[END_REF] that we re-worded. Characteristic 3.4 was split because it included parts corresponding to two domains. The new wording of the characteristics of the levels has highlighted this key difference and now the border between those levels is clear.

If we repeat now the analysis of the problem in Figure 1, question 1a fits new characteristics 2.1, 2.3 and 2.4, because it focus students' attention to draw the diagonals from a vertex of each polygon and count them, so it can be easily solved without being aware of the relationship between the number of sides and diagonals from a vertex. 3.4a. Require some degree of cognitive effort. Although general procedures may be followed, they cannot be followed mindlessly.

Levels of cognitive demand

Domains

Implicit contents

2.3. There may be implicit connection between the algorithms used and underlying concepts or ideas. However, students do not need to be aware of it to solve the problem correctly.

3.4b.

Students need to engage with concepts and ideas that underlie the procedures to complete the problem successfully and that develop understanding.

Explanations 2.5. Require explanations that focus solely on describing the procedure that was used.

Require explanations that focus on the underlying relationships by using specific examples.

Representations

2.6. One or more representations may be used (arithmetical, geometrical, visual diagrams, manipulatives, etc.). When several representations are used, students use them independently, i.e., without establishing connections neither between them nor with the underlying concepts and ideas.

3.3. Usually are represented in multiple ways, (arithmetical, geometrical, visual diagrams, manipulatives, etc.).

To solve correctly the problem, students have to establish connections between different representations by using underlying concepts and ideas, which help them develop meaning.

Table 4: Comparison between the characteristics of problems in two levels of cognitive demand

Question 1a also fits new characteristics 2.2 (since there is no ambiguity about how to solve it) and 2.6 (students will use geometrical and arithmetical representations but without needing to connect them), but it does not fit characteristic 2.5, since this question does not ask for an explanation (so, this analysis is also useful to uncover flaws in the statements of problems). On the other hand, question 1a does not fit new characteristics 3.1, 3.2, 3.3, 3.4a, 3.4b and 3.5. So, now it is clear that question 1a requires a cognitive demand in the level of algorithms without connections, which agrees with our experimental analysis of real students' answers.

Particularizing the new cognitive demand model to specific topics

As mentioned above, the Cognitive Demand model was generated after analysing problems that, in most cases, were related to school arithmetic or algebra. When we tried to use it to analyze problems in other areas of mathematics (plane geometry, geometric pattern problems and visualization), we found that the wording of quite characteristics of the levels were too generic and they did not help us to give meaning to the levels specific to those contexts. This forced us to re-word those characteristics of the levels to mention specific features of a given topic. We present here the particularization we have made to the context of geometric pattern problems.

Geometric pattern problems have proved to be a very fruitful way to introduce basic algebra to students [START_REF] Amit | Rising to the challenge": Using generalization in pattern problems to unearth the algebraic skills of talented pre-algebra students[END_REF][START_REF] Rivera | Teaching and learning patterns in school mathematics[END_REF]. A typical geometric pattern problem presents (Figure 2) a graphical representation of the first terms of a sequence of whole numbers, and asks students to calculate the value of certain terms of the sequence, to verbalize a general procedure to calculate the value of any given term, and to write an algebraic expression to calculate the value of any term.

You can see below a shape made with one dot, another shape made with three dots, and so on.

1. How many dots has the shape in the 4th position? 2. How many dots has the shape in the 6th position? 3. How many dots has the shape in the 20th position? How do you know it? 4. Is there some rule that could allow us calculate the number of dots of any given shape, for instance the one in the 100th position? Justify your answer. 5. Is there some rule that could allow us calculate the number of dots of the shape in the nth position? Justify your answer. We are interested in analysing the relationships among the geometric patterns and the cognitive demand required by different kinds of students' answers. When we first used the definitions of the levels of cognitive demand (Tables 1 and4) to classify answers to geometric pattern problems, we found that some characteristics were meaningless in this context, so we made a complete particularization of the characteristics of the levels to describe the answers to this specific type of problems.

Table 5 presents, as an example, the characteristics of the level of procedures without connections for the context of geometric pattern problems. It may be noted that most characteristics include reference to peculiar and unique aspects of those problems.

Procedures without connections (question 2)

Procedure of solution

• Are algorithmic. The procedure consists in drawing a few terms by following the pattern of the terms in the statement, and counting the items. It can be followed without the need to connect to the arithmetic structure of the sequence. Objective

• Focus students' attention on producing a correct answer, the number of items in an immediate or near term, but not on developing understanding of the structure of the sequence. Cognitive effort

• Solving it correctly requires a limited cognitive effort. Little ambiguity exists about what has to be done and how to do it, because the statement clearly shows how to continue the sequence. Implicit contents • There is implicit connection between the underlying structure of the sequence and the procedure used. However, students do not need to be aware of it and they may answer the question by drawing terms and counting their items. Explanations

• Require explanations that focus only on describing the procedure used. It is not necessary to identify the relationship between the answer and the term.

Representations

• A geometric representation is used to get the number of items and an arithme-tic one to write the result. Students use the representations without establishing connections neither between them nor with the structure of the sequence. This description of the levels of cognitive demand has proved to be very useful to analyze this kind of problems and students' answers to them.

Conclusions

We have presented a case of modification of a theoretical model to adapt it to the specific requirements of the analysis we had to do of our data. The Cognitive Demand model was a pertinent theoretical framework for our research project, with the potential to ground a deep analysis of our data, although the practice showed that the initial definition of this model, as formulated by its authors, did not fit well the requirements of our analysis. We have shown some difficulties that arose when we tried to apply the initial model. The way to overcome these difficulties was to analyze the theoretical model, to identify and understand the origin of and the reason for the difficulties, and to make adequate changes in the definition of the levels of cognitive demand to make it more accurate and useful. Finally, we had also to particularize the new definition of the levels to the specific context of geometric pattern problems. This general way of proceed may be applied, perhaps after an adequate adaptation, to modify other theoretical models not fitting adequately researchers' needs.

Figure 1 :

 1 Figure 1: First part of a problem focused to discover the number of diagonals of any polygon

Figure 2 :

 2 Figure 2: A typical statement of a geometric pattern problem

Table 1 : Definition of the levels of cognitive demand of procedures without connections and procedures with connections (Smith & Stein, 1998, p. 348). Order numbers are added for easy reference

 1

Domains Memorization Procedures without connections Procedures with connections Doing mathematics Procedure of solution

		1.2	2.1	3.2	4.1, 4.5
	Objective	1.1	2.4	3.1	4.2
	Cognitive effort	1.3	2.2	3.4	4.3, 4.6
	Implicit contents	1.4	2.3	3.4	4.4
	Explanations	--	2.5	--	--
	Representations	--	--	3.3	--

Table 2 : Domains of the characteristics of the levels of cognitive demand in Smith and Stein (1998)

 2

Table 5 : Particularization of the Cognitive Demand model to the geometric pattern problems

 5

The results presented are part of the R&D&I research projects EDU2012-37259 (MINECO) and EDU2015-69731-R (MINECO/FEDER), funded by the Spanish Government and the European Fund for Regional Development.Thematic Working Group 17Proceedings of CERME10

Proceedings of CERME10


text:
Yvonne Liljekvist
email: yvonne.liljekvist@kau.se

Mathematics teachers' re-sourcing and use of social media: Can the 'prosumer' concept convey what's going on?

Keywords: Mathematics teachers, prosumer, social media, theoretical discussion

Poster summary

The interrelated roles of social media as both a platform and a phenomenon of interactivity, invite teachers to produce and consume knowledge of teaching and learning mathematics (e.g., [START_REF] Liljekvist | Mathematics teachers' knowledge-sharing on the Internet: pedagogical message in instruction materials[END_REF][START_REF] Van Bommel | Facebook and mathematics teachers' professional development: Informing our community[END_REF], 2016). The availability and user-friendliness of the social media platform alter the behaviour of the mathematics teacher, and 'stories' of the good mathematics teaching are made (e.g. kinds of curricular material, or kinds of questions raised, see e.g., [START_REF] Liljekvist | Mathematics teachers' knowledge-sharing on the Internet: pedagogical message in instruction materials[END_REF]). Analysing the affordances of this new environment is necessary to understand how the subject didactical discourse on learning and teaching is simultaneously constructed and consumed in mathematics teachers' digitalized every-day practice. It is a matter of probing the characteristics of the interaction, that is, the ways in which the activity on the Internet supports knowledge development and re-sourcing in mathematics teaching (cf. [START_REF] Liljekvist | Mathematics teachers' knowledge-sharing on the Internet: pedagogical message in instruction materials[END_REF][START_REF] Ruthven | The re-sourcing movement in mathematics teaching: some European initiatives[END_REF].

The primary aim of this poster is to initiate a discussion in the TWG17 that elaborates on theoretical constructs that may be fruitful in the research of mathematics teachers' digitally extended every-day practice and collaboration. This arena for teacher learning and collaboration is under-researched (see, e.g., Robutti, Cusi, Clark-Wilson, Jaworski, Chapman, Esteley, Gnoos, Isoda, & Joubert, 2016)).

The prosumer concept, that is, people as producers and consumers of products and services (cf. [START_REF] Beighton | Groundhog day? Nietzsche, Deleuze and the eternal return of prosumption in lifelong learning[END_REF][START_REF] Ritzer | The coming of age of the prosumer[END_REF][START_REF] Zajc | Social media, prosumption, and dispositives: New mechanisms of the construction of subjectivity[END_REF] shows some possibilities to theoretically model mathematics teachers' re-sourcing on social media as it centres on the phenomenon per se (i.e., producing and consuming 'value' for the user). Thus it is closely tied to the raison d'être of social media [START_REF] Zajc | Social media, prosumption, and dispositives: New mechanisms of the construction of subjectivity[END_REF] and mathematics teachers' activities there [START_REF] Van Bommel | Facebook and mathematics teachers' professional development: Informing our community[END_REF], 2016). However, the concept needs to be operationalized in an educational setting and in a mathematical discourse in order to have sufficient explanatory power for our purposes. Here are some examples; In business and sociology, the driving forces for investigating 'prosuming' is to understand consumers' behaviour (e.g., [START_REF] Ritzer | The coming of age of the prosumer[END_REF][START_REF] Zajc | Social media, prosumption, and dispositives: New mechanisms of the construction of subjectivity[END_REF], but in educational research mathematics teachers' performance, for instance, as a learner and as a colleague is of interest (e.g., [START_REF] Liljekvist | Mathematics teachers' knowledge-sharing on the Internet: pedagogical message in instruction materials[END_REF][START_REF] Ruthven | The re-sourcing movement in mathematics teaching: some European initiatives[END_REF][START_REF] Van Bommel | Facebook and mathematics teachers' professional development: Informing our community[END_REF], 2016). Further, [START_REF] Beighton | Groundhog day? Nietzsche, Deleuze and the eternal return of prosumption in lifelong learning[END_REF] discusses in his article how the prosumeristical behaviour can also work as a tool for control, where creativity and knowledge development, and professional learning may not be supported. This aspect of mathematics teachers' online activities is relevant, as it, for instance, may explain some of the quality problems in the curricular material shared (e.g., [START_REF] Liljekvist | Mathematics teachers' knowledge-sharing on the Internet: pedagogical message in instruction materials[END_REF].

Mathematics teachers nowadays use social media to re-source and collaborate. This is an arena where the every-day practice of subject didactics is made [START_REF] Liljekvist | Professional Learning Communities in a Web 2.0 World: Rethinking the conditions for professional development[END_REF]. Analysing this activity is to understand teachers as both producers and consumers of subject didactical contributions and of peer-learning. The core research question, then, is how we can theoretically describe mathematics teachers' simultaneous processes of producing and consuming subject didactical knowledge on social media.

Proceedings of CERME10

Acknowledgment

The research was funded by the Swedish Research Council (Dnr. 2015-01979).

Access to the poster: www.kau.se/files/2017-04/CERME_YL.pdf