Ciphertext-only attack (COA) on the d×d$d\times 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(d³26^d2)$O(d^3{26}^{d^2})$ down to O(d13^d)$O(d{13}^d)$.

A rigorous analysis using information theoretic tools is performed.

Simulation results confirm the theoretical analyses.