Giving teeth to expected EC disabling: P2XX(-T)(-ML)

In the detailed discussion regarding the effectiveness of using 192-bit curves as security canaries, concerns are raised about their potential vulnerability to classical attacks and the ambiguity surrounding the timeframe in which more secure 256-bit ECC might also be compromised. The argument posits that if a quantum computer capable of breaking 192-bit encryption exists, the leap to breaking 256-bit encryption could occur rapidly thereafter, making the use of a 192-bit canary potentially misleading. This could result in users mistakenly perceiving the canary's activation as a false positive, thus undermining its intended purpose of early threat detection.

The conversation further delves into the technical aspects of cryptographic challenges, particularly focusing on the Elliptic Curve Discrete Logarithm Problem (ECDLP). It compares two distinct tasks: one where the challenge is to find a scalar a that when multiplied by a given point G results in another point derived from the SHA256 hash of G, and another where a must match a point derived from the hash of varying messages. The former scenario aligns closely with traditional ECDLP definitions, involving a fixed and honestly-sampled target point, while the latter allows for multiple target points generated from arbitrary messages, significantly easing the difficulty of the problem due to the possibility of concurrent attacks on several targets.

The discourse introduces the concepts of single-target ECDLP (ST-ECDLP) and multi-target ECDLP (MT-ECDLP). ST-ECDLP, proposed for use in canary mechanisms, involves a singular, fixed target and is deemed less susceptible to premature or erroneous activation. Conversely, MT-ECDLP reflects scenarios more indicative of real-world conditions where attackers might simultaneously target multiple public keys. This method is considered easier to breach and less ideal for canary constructions due to its susceptibility to various attack strategies that capitalize on the availability of numerous targets.

A suggestion is made to potentially develop a hybrid approach termed limited multi-target ECDLP (LMT-ECDLP), which would restrict the number of permissible target points, thereby offering a compromise between the stringent constraints of ST-ECDLP and the expansive target field of MT-ECDLP. This approach aims to moderate the difficulty of attacks while maintaining a manageable level of security alert efficacy.