We report the study of interactions between cavity photons and paramagnetic Cr$^{3+}$ spins in a ruby (Cr$^{3+}$:Al$_2$O$_3$) Whispering Gallery mode (WGM) resonator. Examining the system at microwave frequencies and millikelvin temperatures, spin-photon couplings up to 610 MHz or about 5% of photon energy are observed between the impurity spins and high quality factor ($Q > 10^5$) WGM. Large tunability and spin-spin interaction allows operation in the strong coupling regime. The system exhibits behaviour not predicted by the usual Tavis-Cummings model because of interactions within the two-level spin bath, and the existence of numerous photonic modes.