Systems and methods that provide relaxivity-insensitive permeability logs. At least some logging system embodiments include a logging tool assembly that measures spin-spin relaxation time distributions of formation fluid nuclei at different positions along a borehole. A processor operates on the measurements to provide a permeability log that is relatively insensitive to relaxivity coefficient changes and hence insensitive to changes in formation fluids. Thus, permeability logs will be relatively unaffected by invasion of the borehole fluids into the formation, even if surfactants in the borehole fluid cause large changes in formation wettability. For each position logged within a borehole, the processor may process the measured relaxation time distribution to determine a Swanson parameter value; adjust the Swanson parameter value to reduce dependence on relaxivity; and convert the adjusted value to a permeability measurement. Examples are included below to demonstrate the markedly increased permeability measurement accuracy.