Suppose $H$ is a hash function; why is $$H(k\mathbin\|H(k\mathbin\|m))$$ not secure?
See this HMAC definition. In there, indeed two keys are used and the mac algorithm is $$H(k_1\mathbin\|H(k_2\mathbin\|m)).$$ Why don't we use $$H(k\mathbin\|H(k\mathbin\|m)),$$ which has only one key?
Alas, there is no simple satisfactory answer to this question. What I can offer is a very strong property that $m \mapsto H\bigl(k \mathbin\| H(k \mathbin\| m)\bigr)$ fails to achieve; a more pedestrian property which even HMAC may or may not achieve but is typically asked to achieve; a reason not to worry about it for any new systems; and some historical background that went into making this mess.
Random oracle indifferentiability. The construction fails to achieve a very strong property, which is convenient for reasoning, but is perhaps stronger than needed for most protocols. Let $H$ be a uniform random function. For any $k$, define $F_k(m) := H(k \mathbin\| m)$; obviously $F_k$ too is a uniform random function for any $k$. There are protocols that are secure when instantiated using $F_k$, but are trivially insecure when instantiated using ${F_k}^2$, where ${F_k}^2(m) := F_k(F_k(m))$. (Of course, you could fix it by using $H(k \mathbin\| 1 \mathbin\| H(k \mathbin\| 0 \mathbin\| m))$—a single bit distinction between the inner and outer hashes.)
This doesn't mean that the protocols are useful in the real world, although they can be contrived[1]—it just means there are counterexamples to the proposition one might hope for that any protocol which is secure when instantiated with $F_k$ is also secure when instantiated with ${F_k}^2$.
Note that the protocols may also fail to be secure with $F_k$ when $H = \operatorname{SHA-256}$, because of the usual length extension attacks on SHA-256. The counterexamples shown in [1] demonstrate that even if $F_k$ had no other attacks like length extension attacks, the mere substitution of ${F_k}^2$ for $F_k$ could cause a secure protocol to become insecure. In contrast, as long as the key is two bits shorter than a block, the HMAC construction is shown indifferentiable in [1]. Of course, so is the much simpler $H(k \mathbin\| 1 \mathbin\| H(k \mathbin\| 0 \mathbin\| m))$.
Pseudorandomness. We considered any fixed key $k$ above, known to an attacker. But the usual security conjecture for HMAC is merely pseudorandomness, where $k$ is secret—this is enough to make HMAC a secure MAC that resists forgery (up to a modest number of messages authenticated[2]), and enough to securely derive secret subkeys from a secret master key using HMAC as in HKDF. Specifically, we conjecture that if $k$ is a uniform random key, then it is hard to tell $\operatorname{HMAC-\!}H_k$ apart from a uniform random function.
As it turns out, the security story traced over the decades in the literature for the pseudorandomness of HMAC for a Merkle–Damgård iterated hash function like MD5 is extremely complicated! In 1996, Bellare, Canetti, and Krawczyk first tried to address it[3] (actually, just the weaker MAC security, not the stronger PRF security) for a double-key variant called NMAC, under the assumption that the underlying compression function is a PRF and is collision-resistant; they then conjectured that deriving two keys from one by ipad and opad oughta be good enough.
For MD5 and SHA-1, the assumption of collision resistance turned out to be unrealistic. In 2006, Bellare revisited the question without assuming collision resistance[4], but with a very complex proof and non-tight bounds that make it unclear concretely how many messages are safe to authenticate with HMAC. They also addressed the security of HMAC's key derivation, but only by assuming that the compression function resists a certain class of related-key attacks—which essentially boils down to assuming the compression function is designed to make HMAC's key derivation secure.
The question was revisited again in 2013 by Koblitz and Menezes[5], and in 2014 by Gaẑi, Pietrzak, and Rybár[6], which incited an academic spat[7][8][9] over the definitions and assumptions that are reasonable for the underlying compression function to give a reasonable security bound for reasonable confidence in the security of HMAC.
The conclusion is that so far, after a quarter century of analysis, nobody has found evidence that HMAC should fail to achieve reasonable PRF security for all reasonable hash functions you might instantiate it with—but the ‘provable security’ framework provides meager confidence with very loose bounds about the PRF-security of HMAC in terms of the PRF-security of the underlying compression function. What does this say about $H(k \mathbin\| H(k \mathbin\| m))$ instead, or $H(k \mathbin\| 0^b \mathbin\| H(k \mathbin\| 1^b \mathbin\| m))$? Who knows!
The bright side. Today, ‘hash functions’ like BLAKE2 and SHA-3 are designed so that the prefix construction $H(k \mathbin\| m)$ makes a secure PRF, and come with built-in PRF modes, keyed BLAKE2 or KMAC, with a theorem relating the security of the PRF to the primitive. So there is essentially no reason to worry about HMAC for any new designs like BLAKE2 or SHA-3.
Historical background.
Kaliski and Robshaw first proposed $H(k \mathbin\| H(k \mathbin\| m))$ in 1995 for IPsec[10], along with $H(k_1 \mathbin\| H(k_2 \mathbin\| m))$ and $H(k \mathbin\| m \mathbin\| k)$, the last of which is sometimes known as ‘envelope MAC’. They picked MD5 because it was new and exciting at the time, and chose these structures to thwart length extension attacks on MD5, and included heuristic security conjectures for the compositions. These heuristics led them to consider deriving $k_i = H(k \mathbin\| i)$ for the two-key case, but they didn't propose it.
Curiously, they were unconcerned with collision attacks on MD5, whose first hints of practicality came the very next year[11], but they were concerned with preimage attacks that might reveal $k$ given $H(k \mathbin\| H(m))$—which is still infeasible today, which should indicate the level of rigor that went into these proposals.
Shortly afterward in 1995, Preneel and van Oorschot described specific attacks on $H(k \mathbin\| H(k \mathbin\| m))$ and other constructions[12], where $H$ is an iterated Merkle–Damgård construction. The attacks don't mean the construction is completely insecure, per se—it just indicated that the cost is less than an ideal MAC.
The crux of what they observed is that if a MAC is constructed by $g(f(\cdots f(f(iv, m_1), m_2)\cdots, m_n))$ for random functions $f$ and $g$, it's collisions in $f$ that spell trouble because they can be extended into collisions of longer messages.* The worst cases are when $g$ is a permutation, which means collisions in $H$ are guaranteed to imply collisions in $f$ which you can turn into many other collisions.
The paper is written in an older style that is a little unfamiliar to the modern norms of cryptography literature. It is phrased as a collection of examples of attacks on the MAC, with cost analyses, rather than as bounds on success probabilities of all possible cost-limited attacks. It concludes with a somewhat baroque construction MDx-MAC that heuristically seems to avoid the attacks.
I won't go into details, but MDx-MAC involves deriving multiple subkeys with ‘envelope MAC’, swapping out the underlying hash function's initialization vectors, changing the constants inside the compression function, etc.—not a very satisfying way to compose a MAC out of a primitive like MD5.
Later in 1996, Bellare, Canetti, and Krawczyk proposed HMAC[13] as we know it today in, e.g., RFC 2104, and offered a preliminary analysis[14] by way of an intermediate two-key construction $\operatorname{NMAC-}\!H_{k_1,k_2}(m) := H_{k_1}(H_{k_2}(m))$. They showed, loosely, that if $H_{k_1}$ is a secure MAC of short messages, and $H_{k_2}$ is collision-resistant (under the somewhat obscure term ‘weakly collision-resistant’; the corresponding ‘strongly collision-resistant’ means ‘second-preimage-resistant’), then $\operatorname{NMAC-}\!H$ is a secure MAC of long messages, by setting a bound on the forgery probability of $\operatorname{NMAC-}\!H$ in terms of the forgery probability of $H_{k_2}$ and the collision probability of $H_{k_2}$.
Note that the double-length key does not imply double-security of NMAC; it just means NMAC needs twice the key material to attain the security attained by an ideal MAC with a single-length key. One could imagine instantiating NMAC by taking MD5, and using $k_1$ and $k_2$ instead of the standard initialization vector. But Bellare et al. figured that people wouldn't want to modify the existing MD5 code they had, so they suggested another approach: use $H((k_1 \oplus \mathrm{opad}) \mathbin\| H((k_2 \oplus \mathrm{ipad}) \mathbin\| m))$. However, they only heuristically conjectured the security of HMAC in relation to NMAC.
* This idea can be taken on its face to suggest a construction for MACs: pick a universal hash family $f_{k_1}$ which merely has low collision probabilities (but from which two outputs, if revealed directly, might trivially determine $k_1$ and enable finding collisions, like Poly1305); pick a short-input, short-output pseudorandom function family $g_{k_2}$ to conceal the output; and use $g_{k_2}(f_{k_1}(m))$. Universal hash families have the advantage that can be extremely cheap to evaluate, e.g. by dot products or Horner's rule in a finite field. (It might even be safe to use $k_1 = k_2$, but I don't know!) Though Preneel and van Oorschot's ideas might have suggested this structure, it attained no practical significance to my knowledge until the development of AES-GCM-SIV decades later[15], by Shay Gueron and our own Yehuda Lindell.
