The search space is small enough that the only "hard" part is telling if the message is properly decoded. They might not have used predictable messages but simply testing for the number of German words / phrases in a given output should work just as well. Assuming the actual messages are not overly cryptic.