which was filled by a large black market that the state absolutely could have legitimized in some way

They largely did legitimize it through measures to formally legalize or informally tolerate it, and that created a class of semi-criminal businessmen often operating with goods, tools, and materials stolen from official supply lines with the tacit acceptance of the authorities, at once causing shortages and also creating a misconception among those privileged enough to buy what they wanted from the second economy that markets were more efficient (since, after all, the guy with smuggled or stolen goods could get them the luxury consumer goods they wanted while the stores lacked them since supply-line theft caused problems for both production and distribution (and that's even before you get into issues with the logistics system itself which were generally covered up by black market trading of excess materials, preventing the central planning system from being able to fix distribution problems).

It also only really stagnated compared to its previous rapid growth, and that was mostly a result of shifting industrial production from building more industrial capital to focusing more on consumer goods. They were always going to slow their growth at some point, but Khrushchev and his bloc began that process prematurely, before a sufficient industrial base had been built up. Compared to the US, they were still growing faster and on track to reach parity within a few decades, they just lacked the increasing flow of wealth the US was extracting from the periphery.