Electrons can be accelerated to ultrarelativistic energies at strong (high-Mach number) collisionless shock waves that form when stellar debris rapidly expands after a supernova. Collisionless shock waves also form in the flow of particles from the Sun (the solar wind), and extensive spacecraft observations have established that electron acceleration at these shocks is effectively absent whenever the upstream magnetic field is roughly parallel to the shock surface normal (quasi-parallel conditions). However, it is unclear whether this magnetic dependence of electron acceleration also applies to the far stronger shocks around young supernova remnants, where local magnetic conditions are poorly understood. Here we present Cassini spacecraft observations of an unusually strong solar system shock wave (Saturns bow shock) where significant local electron acceleration has been confirmed under quasi-parallel magnetic conditions for the first time, contradicting the established magnetic dependence of electron acceleration at solar system shocks. Furthermore, the acceleration led to electrons at relativistic energies (~MeV), comparable to the highest energies ever attributed to shock-acceleration in the solar wind. These observations demonstrate that at high-Mach numbers, like those of young supernova remnant shocks, quasi-parallel shocks become considerably more effective electron accelerators.