Has any research been done on CryptoNight? How secure is it, in terms of having a flaw that would allow PoWs to be produced free or cheaply, independent of difficulty?
This annotated whitepaper acknowledges the importance of a thorough review:
Constructing a hash function is difficult; constructing a hash function satisfying these constraints seems to be more difficult. This paper seems to have no explanation of the actual hashing algorithm CryptoNight.
Nic van Saberhagen describes loosely some properties of a proof of work algorithm, without actually describing that algorithm. The CryptoNight algorithm itself will REQUIRE a deep analysis.
According to Monero Core Developer Smooth:
CryptoNight (and the code implementing it) was extensively reviewed, though not as part of a "formal" review process, by Professor David Andersen (known as 'dga' in crypto circles) who also wrote the current implementation of the hashing code. He found nothing wrong with the design and largely praised it, stating that it would likely achieve its goals of resisting extreme optimizations and narrowing (but not eliminating) the performance gap between CPUs, GPUs, and ASICs.
I have seen hints (mostly in the form of offhand comments) that other experts have reviewed without finding problems, or at least no major problems, but that is not a formal review, especially if they don't publish their results.
Monero Research Lab helps to identify problems and find solutions. Currently they have higher priority matters than spending more time focusing on CryptoNight:
As of this writing, the algorithm employed for difficulty adjustment in the CryptoNote reference code is known by the Monero Research Lab to be flawed. We describe and illustrate the nature of the flaw and recommend a solution. By dishonestly reporting timestamps, attackers can gain disproportionate control over network difficulty. We verify this route of attack by auditing the CryptoNote reference difficulty adjustment code, which, we reimplement in the Python programming language. We use a stochastic model of blockchain growth to test the CryptoNote reference difficulty formula against the more traditional Bitcoin difficulty formula. This allows us to test our difficulty formula against various hash rate scenarios.