I show that nondecreasing entropy provides a necessary and sufficient condition to convert the state of a physical system into a different state by a reversible transformation that acts on the system of interest and a further "catalyst," whose state has to remain invariant exactly in the transition. This statement is proven both in the case of finite-dimensional quantum mechanics, where von Neumann entropy is the relevant entropy, and in the case of systems whose states are described by probability distributions on finite sample spaces, where Shannon entropy is the relevant entropy. The results give an affirmative resolution to the (approximate) catalytic entropy conjecture introduced by Boes et al. [Phys. Rev. Lett. 122, 210402 (2019)PRLTAO0031-900710.1103/PhysRevLett.122.210402]. They provide a complete single-shot characterization without external randomness of von Neumann entropy and Shannon entropy. I also compare the results to the setting of phenomenological thermodynamics and show how they can be used to obtain a quantitative single-shot characterization of Gibbs states in quantum statistical mechanics.