Ciphertext-only attack (COA) on the d×d Hill cipher is studied.
A common belief repeated in several modern crypto textbooks about security of Hill against COA is disproved.
Computational complexity of COA is dramatically reduced from O(d326d2) down to O(d13d).
A rigorous analysis using information theoretic tools is performed.
Simulation results confirm the theoretical analyses.