  For Arithmetization-Oriented ciphers and hash functions Gr\"obner basis
attacks are generally considered as the most competitive attack vector.
Unfortunately, the complexity of Gr\"obner basis algorithms is only understood
for special cases, and it is needless to say that these cases do not apply to
most cryptographic polynomial systems. Therefore, cryptographers have to resort
to experiments, extrapolations and hypotheses to assess the security of their
designs. One established measure to quantify the complexity of linear
algebra-based Gr\"obner basis algorithms is the so-called solving degree.
Caminata \& Gorla revealed that under a certain genericity condition on a
polynomial system the solving degree is always upper bounded by the
Castelnuovo-Mumford regularity and henceforth by the Macaulay bound, which only
takes the degrees and number of variables of the input polynomials into
account. In this paper we extend their framework to iterated polynomial
systems, the standard polynomial model for symmetric ciphers and hash
functions. In particular, we prove solving degree bounds for various attacks on
MiMC, Feistel-MiMC, Feistel-MiMC-Hash, Hades and GMiMC. Our bounds fall in line
with the hypothesized complexity of Gr\"obner basis attacks on these designs,
and to the best of our knowledge this is the first time that a mathematical
proof for these complexities is provided.
  Moreover, by studying polynomials with degree falls we can prove lower bounds
on the Castelnuovo-Mumford regularity for attacks on MiMC, Feistel-MiMC and
Feistel-MiMC-Hash provided that only a few solutions of the corresponding
iterated polynomial system originate from the base field. Hence,
regularity-based solving degree estimations can never surpass a certain
threshold, a desirable property for cryptographic polynomial systems.
